There are $n$ light bulbs with connection between them. Each light bulb have a switch that when you press it you turn on\off the light bulb and every other light bulb that connected to her. Prove that you can turn on all the light bulbs from the initial state that everyone is off.
First I assume that the graph is connected because if he is not we can just do the same for each connected component afterwards I tried to prove that using induction but I got stuck after the base case.
Induction is the right approach here? if so can you give a hint how to continue and if not can you tell me how I should approach this?
A proof by induction on the amount of light bulbs $n$.
the first step is trivial, so let $G$ be a setting of $n$ bulbs with arbitrary connections. due to the induction hypothesis, we have a solution for each set of $n-1$ bulbs in G, if one of these solutions turns out to also leave the n'th bulb on then we are done, otherwise we are left with a one-to-one bijection between bulbs and solutions that leave only one bulb off. now we have two cases, $n$ is even or $n$ is odd.
$n$ is even: all we need to do is to iterate over all $n$ solutions in our bijection, each bulb gets its state changed by $n-1$ of these solutions, and since $n-1$ is odd, all bulbs will be on by the time we finish iterating.
$n$ is odd: we can use the fact that every graph has an even amount of vertices with odd degree. we will iterate over only the solutions in our bijection that leave a bulb with odd degree off. there is an even amount of these solutions, so each bulb with odd degree will be on after this iteration (since one of the solutions don't affect it), while each even bulb will be off (affected by all solutions). from this state, all we need to to is to "click" on every bulb. even bulbs will have their state changed an odd amount of times (one for each neighbor and one for themselves) while odd bulbs will be left in the same state. all bulbs are now on.