# Check existence of walk visiting every node in graph odd-times

Lets have an undirected connected graph G(N,E) and pair of colors {C1,C2}

Assign every node the color C1. Every time an node is visited, color is flipped (from C1 to 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-times where n is odd)?

## 1 Answer

The spine of a tree $T$ is the tree we obtain by simultaneously removing all leaves of $T$.

Let $T$ be a spanning tree of $G$. Start walking anywhere and visit every leaf exactly once, returning to a vertex that belongs to the spine of $T$. Now remove all leaves, continue your walk and visit every leaf of the new tree that has been visited an even number of times. Again return to a vertex that belongs to the spine of your current tree. Continue until you are left with a spine that is either a $K_2$ or a star and treat that case specifically (it is not hard).