Lets have an undirected connected graph
G(N,E) and pair of colors
Assign every node the color
C1. Every time an node is visited, color is flipped (from
C2 and vice versa).
How can I check if there exist a
walk which leaves all nodes colored with
C2 after traversing?
Existence of Eulerian path or circuit can be check by checking counts of odd and even node degrees. Can be similar rule formed for this case (Visiting all nodes exactly
n is odd)?