# Proving that disconnecting edges of a 3-edge-colorable graph are of the same color

I'm struggling to prove the following:

Edges of a connected cubic graph G can be colored with 3 colors in such a way that no adjacent edges are of the same color. 2 edges were removed from the graph making it disconnected. Proof that those edges were of the same color.

I've found an example of a cubic graph with two edges that disconnect it, and tried to color them with different colors and failed to do that, but I'm not sure how to prove that. Proceed by contradiction. Let $$H$$ be $$G$$ after removing the two edges.

Take a connected component $$C$$ of $$H$$ and assume $$e$$ is a removed edge from a vertex $$x$$ in $$C$$ to a vertex not in $$C$$.

Also assume $$e$$ is blue and the other removed edge is green.

Let the other color be red. Note that the red edges with endings in $$C$$ form a matching of $$C$$ so $$|C|$$ is even.

On the other hand the blue edges with endings in $$C$$ form a matching of $$C\setminus \{x\}$$ so $$|C|-1$$ is even.

• By $C∖{x}$ do you mean $C - x$ (graph induced by $C∖{x}$)? Apr 18, 2022 at 1:50