Let there be a square, connected with 9 dots and 12 lines. We can select some lines (at least 1, maximum 4) among the 12 lines, and then remove them. In how may ways can we remove lines such that all dots will still be connected?
Attempt:
The number of ways of selecting lines (maximum of four lines) is: $\binom{12}{1} + \binom{12}{2} + \binom{12}{3} + \binom{12}{4}$. We can first calculate the number of ways of selecting lines such that the removal makes the dots disconnected. Let us consider 4 cases:
Selecting exactly one line. There is no selection of one line such that the removal makes the dots disconnected.
Selecting exactly two lines. Notice there are only 4 selections that makes the dots disconnected, each of this is the selection of two lines connected by the corner dots. So the number of ways is $$ 4 $$
Selecting exactly three lines. We can pick two lines from a corner, and one line from any of the other 10 lines. Since there are 4 corners, so it will be $10 \times 4$. Also, we can remove the 3 lines connected to a dot at the middle of a side (total of 4 sides), this will make the square disconnected. So the number of ways is $$ 4 + 10 \times 4$$
Selecting exactly four lines. We find the number of ways to disconnect the dots as below: 1) Remove 1 line first that immediately disconnect the dots, and then pick any 3 lines. 2) Remove 2 lines first that immediately disconnect the dots, and then pick any 2 lines. 3) Remove 3 lines first that immediately disconnect the dots, and then pick any 1 line. 4) Remove 4 lines that immediately disconnect the dots. For case 1), we cannot pick one line that disconnect the dots. For case 2), we can select two lines at top left corner, and two more lines from the remaining 10. Similarly for the other 3 corners, this sums up to $4 \binom{10}{2} - \binom{4}{2}$. For case 3) we can remove first the three lines connected to the middle dot at the left side, plus one line from the others except lines that connected to the top left or bottom left, this means $7$. Multiply by 4 because of 4 sides. for case 4) we can remove the 4 lines connected to the center, and the square is disconnected. Finally, So the total number of selections for making the dots disconnected is: $$ 0 + \left( 4\binom{10}{2} - \binom{4}{2} \right) + 7 \times 4 + 1 $$
So the total number of selections for the main problem is:
$$\binom{12}{1} + \binom{12}{2} + \binom{12}{3} + \binom{12}{4} - \left( 4 + (4 + 10 \times 4) + \left( 4\binom{10}{2} - \binom{4}{2} \right) + 7 \times 4 + 1 \right) $$
Is this correct, or are there better approaches?
For the case of $4$ segments deleted I made use of the GAP system (tag added). I made use of the following $12 \times 9$ incidence matrix: $$\begin{pmatrix} 1 & -1& 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & -1& 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & -1& 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & -1& 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & -1& 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & -1\\ 0 & 1 & 0 & 0 &-1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & -1& 0 & 0 &, 0\\ 0 & 0 & 0 & 1 & 0 & 0& -1& 0 &, 0\\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & -1& 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & -1\\ \end{pmatrix}$$ the columns represent the dots and the rows the edges. I choose to use directed edges in order to easily get rid of cycles. For each of the $495$ combinations of rows I proceeded as follows:
1) First I got rid of occasional cycles by using the GAP command "BaseMat", this function removes rows that are lineraly dependent on others, so that we are left with linearly independent rows (no cycles).
2) I removed all the $-1$ by $1$ in order to make the remaining steps easier.
3) I looked for columns that had only one entry. I determined the row where this entry occured and replaced this entry with zero. In this row I localized the second entry and determined if there was another entry in its column. If this was the case then I removed the row. This has as a result that when a segment has a free endpoint but is attached to another segment it can be removed (his is what is called in homotopy theory a "retraction") . 4) I repeated step 3 until more retraction was't possible. Ending up with only one row left pointed to a connected graph, otherwis to a non connected graph.
The result gave $108$ non connected graphs as seen here
The other cases can be seen here, 2, 3 and 4