- #1
math8
- 160
- 0
How can you prove that a cubic graph with a bridge cannot be 3-edge colored?
I guess one could try a proof by contradiction, so we assume a 3 edge coloring is possible for such a graph. But then I am not sure in which direction to continue. I have tried to draw such graphs, and clearly, they can't be 3 edge-colored. But a more formal proof would be helpful.
Or maybe a proof by contrapositive, so let say we have a cubic graph with a 3-edge coloring. How do we show this graph is bridgeless?
I guess one could try a proof by contradiction, so we assume a 3 edge coloring is possible for such a graph. But then I am not sure in which direction to continue. I have tried to draw such graphs, and clearly, they can't be 3 edge-colored. But a more formal proof would be helpful.
Or maybe a proof by contrapositive, so let say we have a cubic graph with a 3-edge coloring. How do we show this graph is bridgeless?