The standard proof does use nodes and arcs (or vertices and edges, which I am taking to mean the same thing). A proper coloring must assign distinct colors to

The standard proof does use nodes and arcs (or vertices and edges, which I am taking to mean the same thing). A proper coloring must assign distinct colors to neighboring vertices, but this doesn't mean that vertices with the same color are identified. Here's an overview of the simplest version of the proof as of 1998: http://www.ams.org/notices/199807/thomas.pdf http://www.ams.org/notices/199807/thomas.pdf . This should shed some light on why the proof is as complicated as it is. (See especially the section on equivalent formulations.)