Graph containing bridge An edge $e$ is a bridge in a connected graph $G$ if the graph $G-e$, which is obtained from $G$ by removing $e$, is not connected. Show that each graph which has a bridge contains at least two vertices with odd degree.

Assume by contradiction this is not true. Then all vertices have even degree.
Now remove the bridge. Then, the end vertices of the bridge have odd degree, and all the other vertices have even degree. And you get a graph with two components.
But each component contains exactly one of the end vertices of the bridge, therefore exactly one vertex of odd degree. This is impossible, contradiction.
