Skip to main content
1 of 2
Fedor Petrov
  • 108.9k
  • 9
  • 264
  • 459

Counterexamples are, for example, complete graphs with even number $2k$ of vertices. If we manage to color such a graph with $2k$ colors, then all vertices have different colors, and from each vertex of color, say, $s$, there is exactly one edge of each color except $s$. Therefore total number of edges of color $s$ is $(2k-1)/2$, this is not possible.

Your observation on clique number is correct: each clique either contains at least two edges and at most one vertex, or it contains unique edge at at most 2 vertices, or it contains only vertices. All cases are clear.

Fedor Petrov
  • 108.9k
  • 9
  • 264
  • 459