# Determining segments needed for a (not quite) connected 3x3 square graph

I am writing a text adventure where I want to track how many guardians you need to dispel to open everything up. (edited to add) That's easy to add with a static graph, but I wanted to see what happened if someone got rid of a few guardians.

I've had to use a lot of test cases to get what I want, and I'm worried about mistakes, or if there is an easier way.

The map is below. In the game, the player must dispel the 2-3 guardian as well as 3-6, to help a person at 3 escape. Guardians guard passages between x and x+3, as well as x and x+1 if x mod 3 != 0.

1-2*3
| | *
4-5-6
| | |
7-8-9

The player starts at 7, and they need to gain access to 1, 3, 5 and 9 in any order.

Is there a formula or method to figure things out, or do I need to use brute force? My current solution is:

• if you haven't tackled any guardians, the answer is 5. Otherwise, start with a total of 0.
• if 5 is not visited, add 1 to the total.
• if 1 is not visitable, add 1 to the total.
• Also, if 2 and 4 are not visitable, and 6 is, add another 1.
• if 9 is not visitable, add 1 to the total.
• Also, if 6 and 8 are not visible, and 2 is, add another 1. (these "add another one" cases are for if you go, say, 7-4-5-2. A 5-2 or 5-6 may do double duty in some cases.)
• if 2 and 6 are not visitable, add another 1.

This seems to work in a lot of cases. However, I can't be sure I've got them all. The player also doesn't need to access both 2 and 6, or both 4 and 8 for that matter. You can see that by letting the player destroy the guardians 1-2 2-3 2-5 5-8 7-8 8-9 (in an I) or rotate that 90 degrees. So it seems there are special cases, and I'm wondering if there's a non-hairy way to tackle this.

I am not sure that I have understood what are you asking for. I can say the following about a minimal number of segments (we call them edges) needed to open everything up and their pattern. The required subgraph $G$ should contain distinguished vertices $1$, $3$, $5$, $7$, and $9$, which constitute an independent set (that is, no two of them are adjacent). So in order to make $G$ connected we have to choose for each of distinguished vertices at least one incident edge (and both edges incident to the vertex $3$ to help a person at $3$ escape). Thus we have already used six edges. But this is still not enough to make $G$ connected. Indeed, $G$ may not contain at most one of vertices $4$ and $8$ (and already contains all other vertices). Thus $G$ has at most eight vertices, so in need to have at least seven edges to be connected. An instance of seven edges, solving the problem, is