3
$\begingroup$

I would like to prove that the chromatic index of a graph with vertices of degree 3 and one vertex of degree 2 is 4.

I know:

  • That this graph is in fact 3-regular graph (cubic graph) with one edge subdivided.
  • That this graph has odd number of vertices.
  • That its chromatic index is 3 or 4 (from Vizing's theorem), so I it would suffice to prove that its chromatic index can't be 3.

Any advices?

$\endgroup$
3
$\begingroup$

Suppose you have a proper $3$-coloring of the edges: each vertex is incident with a red edge, a blue edge, and a green edge, except the vertex of degree $2$, which is incident with a red edge and a blue edge. Then the degree-sum of the red subgraph is $n$ (the number of vertices), while the degree-sum of the green subgraph is $n-1$. This is impossible, because both degree-sums have to be even.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.