Is it possible to find a sequence to make all values 1 for a graph where nodes with binary values have exactly 2 directed incoming and outgoing edges

graph theory

Hello everyone I asked this question here before, but I would like to share it again.

Imagine a graph with N nodes and each node has exactly 2 leaving directed edges and 2 incoming directed edges. Each node can take values {0,1}.

Now here is the catch, at the start all nodes have value 0 . You can visit a node however you like but when you visit a node it's value and it's connected nodes with 1 edge changes their values. Is it possible to follow a sequence where one makes all nodes values 1.

For example:

There is a graph like:

Nodes = {A,B,C,D,E}
Edges = {A -> B, A -> C,  
         B -> C, B -> D, 
         C -> D, C -> E, 
         D -> E, D -> A,
         E -> A, E -> B }

Now when we follow sequence {A,B,C,D,E} values of each node will be as follows:

A B C D E
1 1 1 0 0
1 0 0 1 0
1 0 1 0 1
0 0 1 1 0
1 1 1 1 1

As you can see at last visit all nodes became 1.

So what I want to figure out is, is it possible to find a sequence for all possible graphs generated by the rules mentioned above?

How can I prove or disprove this? Any help would be appreciated. Thank you!

Best Answer

Some graphs may have shorter solutions, but visiting every node once will always work (with the conditions you've specified). Each node will change its value three times: once when you visit that node, and once when you visit the source of each of its incoming edges. So the value of that node will go from $0$ to $1$ to $0$ to $1$.

For an example of a graph where a shorter solution exists, consider the graph with nodes $A$, $B$, $C$, $D$, $E$, $F$ and twelve edges:

  • The six edges $A \to B$, $B \to C$, $C \to D$, $D \to E$, $E \to F$, $F \to A$;
  • The six edges $A \to C$, $B \to D$, $C \to E$, $D \to F$, $E \to A$, $F \to B$.

Then visiting nodes $A$ and $D$ is enough to toggle all six nodes, due to the edges $A \to B, A \to C, D \to E, D \to F$.

Related Question