MathCastle
Graph TheoryMediumGraph Coloring

Graph Coloring · Medium problem

Take K5K_5 (five mutually linked vertices) and remove just ONE edge, say the one between vertices 33 and 44 (99 links remain, out of the 1010 in K5K_5). Unlike K5K_5 itself, this graph IS planar (it satisfies the planar edge bound E≤3V−6E\le3V-6 exactly, with 9=3(5)−69=3(5)-6). What is its chromatic number?