MathDB
Unique 3-coloring of a graph

Source: Kürschák 2003, problem 2

July 8, 2014
combinatorics unsolvedcombinatorics

Problem Statement

Prove that if a graph G\mathcal{G} on n≥3n\ge 3 vertices has a unique 33-coloring, then G\mathcal{G} has at least 2n−32n-3 edges.
(A graph is 33-colorable when there exists a coloring of its vertices with 33 colors such that no two vertices of the same color are connected by an edge. The graph can be 33-colored uniquely if there do not exist vertices uu and vv of the graph that are painted different colors in one 33-coloring, yet are colored the same in another.)
Back to ProblemsView on AoPS