Showing inductively that a light switch situation leads to graphs with the same number of connected components

Question

I would like to know how to prove that a situation leads to the same number of connected components in a graph, in the general case.

It has to do with the number of light switches controlling a lightbulb. Imagine we have a setup like the one shown here: .

There are two light switches controlling a single lightbulb. A light switch can be in the "up" state or the "down" state. The lightbulb may also be in the "on" state or the "off" state. Because this situation has 3 different things, each one having the possibility of being in one of 2 states, the total number of situations for two light switches is $2^{2+1}=8$, as shown in the following table:

| State | S1   | S2   | Bulb |  
|-------|------|------|------|
|   1   | Down | Down | Off  |  
|   2   | Down | Up   | Off  |  
|   3   | Up   | Down | Off  |  
|   4   | Up   | Up   | Off  |  
|   5   | Down | Down | On   |  
|   6   | Down | Up   | On   |  
|   7   | Up   | Down | On   |  
|   8   | Up   | Up   | On   |    
|-------|------|------|------|  

From this it is possible to think about the possible transitions between the states. When a switch is flipped, it changes state to either up or down depending on where it was before, and the lightbulb turns off or on depending on where it was before too. The transitions between the states are summarized in the following table, with each row being the set of states it can transition to:

| State | Transition States | 
|-------|-------------------|
|   1   | { 6, 7 }          |
|   2   | { 5, 8 }          |   
|   3   | { 5, 8 }          |
|   4   | { 6, 7 }          |
|   5   | { 2, 3 }          |
|   6   | { 1, 4 }          |
|   7   | { 1, 4 }          |
|   8   | { 2, 8 }          |
|-------|-------------------|  

From this a graph can be made between the states and the states it can transition to. The graph for two light switches is here:

As it turns out, this graph has two connected components:

This means that depending on the starting state of this system, you can only reach half of the states.

The interesting thing is that, if you repeat this problem with more light switches controlling a single lightbulb, whether that be 3 switches, 4 switches, or even 10 switches, the graph that is made continues to have only two connected components, whether or not there are an odd number of switches.

What is also strange is that if you create the adjacency matrix for these graphs, there is a repeating pattern. The adjacency matricies for the 2 switch case shows up in the 3 switch case, the 4 switch case shows up in the 5 switch case, and so on. It is seen in these images (Some of these are small):

2 switches:

3 switches:

4 switches:

5 switches:

6 switches:

(There are images up to 11 switches but I can only post so many links.)

The images show that adjacency matrices of previous switch counts show up in later switch counts. There are also only two connected components for each of these situations, even with 10 switches, in which the number of states is $2^{10+1}=2,048$!

I am asking, essentially, how to go about trying to prove:

The number of connected components in the resulting transition graph for N light switches is always 2.

Alternatively, if there are similar problems to this that I could study, what are those similar problems? I am not too familiar with graph theory.

Answer 1

The basic principle at work here is "invariants". An invariant is something that doesn't change when you apply an operation.

If we find some property of the system that doesn't change when you flip a switch, but is different for two states, this proves that you can't get from one state to the other by flipping switches.

In this case, the invariant is binary: "odd" versus "even". (This is a common situation.) Assign a value of $0$ to switches that are down and $1$ to switches that are up; assign a value of $0$ to the light when it's off and $1$ when it's on. (This is arbitrary; any assignment of $0$ or $1$ would work.) Add up these numbers to get the total value of a state. Then in the $2$-switch problem:

• States $1, 4, 6, 7$ have an even total value ($0$ or $2$).
• States $2, 3, 5, 8$ have an odd total value ($1$ or $3$).

Additionally, flipping a switch changes its value by $1$, but also changes the value of the light by $1$, so the total change is either $0$ or $\pm 2$. This means that if the total value starts even, it remains even forever; if it starts odd, it remains odd forever.

The same thing happens with any number of switches.

Of course, this doesn't prove that there are only two connected components, and not more. Maybe there's some other invariant we've missed. You should prove that if two states both have even total value, or if they both have odd total value, you can get from one to the other.

How do we find the invariant? Knowing where to look comes with experience. But whenever a graph of states has $k$ connected components, we expect that there's some invariant with $k$ possibilities to find. This often comes from doing arithmetic modulo $k$. This is especially true when $k=2$, in which case we can often identify some property of the state as being "odd" or "even". Then it's just a matter of cooking up something that doesn't change.

Answer 2

Represent the states as binary strings, with a $1$ representing a switch flicked up or the light bulb being on, and $0$ representing down/off. For example, switch $1$ and $3$ being up, switch $2$ being down, and the bulb being on, would be represented by the binary string $1011$.

Now, define a function from the set of states to $\{0, 1\}$ that is the sum, modulo $2$, of all $1$s in the string. That is, $0$ represents an even number of $1$s in the state, and $1$ represents an odd number of $1$s in the state.

Every valid transition involves changing the last bit in the string, as well as one of the other bits. There are three possibilities:

1. Two $1$s are changed to $0$s,
2. Two $0$s are changed to $1$s,
3. One $0$ and $1$ swap their values.

In case 1, there are two $1$s lost. In case 2, there are two $1$s gained. In case $3$, the number of $1$s remains unchanged. In any case, the function value doesn't change! You can only transition between states that evaluate to $0$, or transition between states that evaluate to $1$. This means your graph is disconnected, i.e. has at least two connected components.

The last thing to prove is that there is a path between every two states that evaluate to $0$, and similarly for $1$. This will establish that there are exactly two connected components. I'm not going to do this, but you can essentially perform transitions to change each each bit from the first state to the second state. Change each bit, in turn, from leftmost to rightmost. The light bulb bit will change with it, but will always come out correct, as both states have the same function value.