Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

3-regular (cubic) graphs with a bridge

  1. Sep 18, 2011 #1
    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?
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted