coloringcombinatoricsdiscrete mathematicsgraph theorygraph-connectivity
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.
Your 'proof' would show that any graph is 5-colorable. You found the weakness already: you cannot just 'independently' add back the old cycles: they will interfere.
Take a cellular embedding of $K_5$ in the torus, and turn it into a cubic graph by replacing each vertex by a $4$-cycle. Here's what this might look like:
The result is $3$-edge-colorable: color the edges of each $4$-cycle using two of the colors, and use the third color on the long edges.
However, the faces of this embedding are not $4$-colorable. You can check that any two of the large faces of length $8$ are adjacent to each other (and therefore coloring all $5$ of these faces takes $5$ distinct colors).
Best Answer
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.
A contradiction.