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.