# Proof for a simple graph puzzle

First up apologies if this is the wrong board to post on, there are too many stack exchanges :P This problem comes in 5 parts, the only required part is part 1 but there are plenty of internet cookies available for those that attempt other parts. The extra parts can be done in any order.

Setup:
The rules are simple, you have a graph with n nodes and e edges connecting the nodes together. There wont be any duplicate edges. Each node has a binary state of true or false and each node may start in either state. The aim is to get all nodes set to true however each time you flip the state of a node it also flips any connected nodes. A flip constitutes a move and you may take as many moves as you would like.

Example:
Green is true and red is false
Starting state: View Example 1
This puzzle could be solved in 1 move by flipping the node in the top right. However for the sake of this example lets say I’m really bad at this puzzle and chose to flip the top left node, it would also flip the top right node and the bottom node:
View Example 2

This puzzle was solvable in just 1 move.

Example 2:
It is however possible to construct a puzzle that is impossible, take the puzzle below as an example. It doesn’t matter how many flips you do as there are only 2 possible states and neither result in the success state.
Example 3 has to be directly linked as I can't post more than 2 links:
i.stack.imgur.com/Es61y.png

Problem 1:
I am looking for an algorithm/equation to determine whether a given graph is possible, just a true or false, that’s it.

Problem 2:
Once you know it’s possible I would line to know the minimum number moves required for the solution.

Problem 3:
If you impose a limit on how many times you may flip a node can you come up with updated solutions to parts 1 and 2

Problem 4:
Similar to part 3, how does your solution change when you can have directional edges that only pass a flip along in a certain direction,

Finally Problem 5:
What are the moves required to solve the puzzle

Conclusion:
I should clarify that I have no idea if the problems above are solvable. They seem like they should be but it’s been too long since I have done graph theory and I don’t have the time to redo the syllabus. Best of luck to those who give it a go and happy problem solving.

• This is called the "lights out" puzzle. It and its variants are very well studied. See pdfs.semanticscholar.org/dc08/… as a quick reference to the graph version of the problem. – Bob Krueger Jun 8 '17 at 17:39
• "very well studied" might be an overstatement. I have seen active research on the puzzle and its variants, but it is certainly not complete enough to answer all of your questions in the general graph context. – Bob Krueger Jun 8 '17 at 17:43
• For problem 3, there is never any advantage in flipping a node more than once as two flips returns you to where you started and the flips commute. A solution is just a list of nodes to flip. That means there are a finite number of possible solutions to try, just $2^n-1$ – Ross Millikan Jun 8 '17 at 17:52
• @Bob1123 Ofc I come up with a puzzle that already exists -_-. I will read through that doc you linked but after having a skim it seems awfully confusing. – Andy A Jun 8 '17 at 18:24
• @RossMillikan I was hoping for something with less brute force, and I'm not entirely sure your observation about multiple flips is true but I am yet to come up with an example that goes against this assumption. – Andy A Jun 8 '17 at 18:27