How can you prove that a cubic graph with a bridge cannot be 3-edge colored?(adsbygoogle = window.adsbygoogle || []).push({});

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?

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# 3-regular (cubic) graphs with a bridge

Can you offer guidance or do you also need help?

Draft saved
Draft deleted

Loading...

Similar Threads for regular cubic graphs |
---|

I Representing Tiling and Packing Solutions |

**Physics Forums | Science Articles, Homework Help, Discussion**