0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Your choice of words is unusual. Does "link" mean "edge"? Does "related" mean "connected"? $\endgroup$ – Sammy Black May 15 '14 at 19:56
  • $\begingroup$ Well, after the edit, my comment seems strange. :-) $\endgroup$ – Sammy Black May 15 '14 at 19:56
  • 1
    $\begingroup$ I just hope pounds mean vertices! $\endgroup$ – Casteels May 15 '14 at 19:57
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.