Step 02: We arbitrarily pick a node and colour it red.

Step 03: Pick an edge and follow it. Colour in the new vertex green. We don't need to mark the edge within the code, per se. It is coloured in this demonstration to signify "resolved" edges to ease human consumption. =)

Step 04: Only one place to go at this step... alternate colours.

Step 05: Etc.

Step 06: Etc.

Step 07: Etc.

Step 08: Etc.

Step 09: Etc.

Step 10: Finally, something new! Here, we try to go to a vertex which is already coloured. That's not allowed, so we put this edge (1) in our list of conflicted edges.

Step 11: Back on the move again...

Step 12: And another conflicted edge. Note that this is the last edge coming out of this particular vertex...

Step 13: Now we've backtracked (resursively) and have ended up near the "X" in the graph, where we find another conflicted edge (3).

Step 14: Back on the move...

Step 15: Note a couple of conflicted edges...

Step 16: Take care of another path and conflict...

Step 17: By now, you get the point. Backtrack, note a conflict, backtrack, fill in some vertices, note a final conflict... in the end we end up with the above spanned graph. Next we will work on the conflicted edges.

Edge 1: No conflict here! This edge is okay.

Edge 2: This one's good, too.

Edge 3: Ah ha, not so good. We look at the lower left vertex first: it has red and green neighbors. So does the upper right vertex. So, we make a new colour (orange) and give it to the lower left vertex.

Edge 4: Upper left and lower right both have orange, red, and green neighbors. So we make a new colour, purple, and give it to the upper left vertex (it has more conflicted edges).

Edge 5: Although they were conflicted when all we had was a spanning tree, these two vertices aren't conflicted now. So this edge is okay as-is.

Edge 6: We check the upper left vertex first (it has a higher degree). It has red, orange, and green neighbors - but no purple! So, we make it purple.

Edge 7: No conflict here...

Edge 8: ...Nor here. As this was our last conflicted edge, we're done colouring the graph. In this example, it took four colours. This is minimal, as K4 is present as a subgraph.