MathCastle
Graph TheoryHardGraph Coloring

Graph Coloring · Hard problem

The "house" graph has vertices 1,2,3,4,51,2,3,4,5 with edges 12,23,34,4112,23,34,41 (a square) and 15,2515,25 (a triangular roof over edge 1212), 66 edges in all. A painter has 44 colors available and colors the 55 vertices so that adjacent vertices always differ. In how many of these proper colorings is EVERY one of the 44 colors actually used at least once?