5
$\begingroup$

Prove that every connected graph of all whose vertices have even degree contain no bridges.

I tried to prove this by induction. So let $G$ be a connected graph of order $n$. Since all vertices of $G$ have even degree, $n \geq 3$.

Base $n=3$ we have $C_3$, so every edges lie on a cycle thus, non of those edges can be bridge.

Assume that this is true for $n=k$, let $h$ be a graph obtained by adding 2 vertex $a,b$ to $G$ and joining $a,b$ to every vertex in $G$ so that every vertex in $G$ still have even degree. Since the statement is true for $n=k$, $G$ has no bridge, meaning very edge of $G$ lie in some cycle. Now when we add some edge $e_{a_1},e_{a_2},..., e_{a_k}$ from $a$ to $u \in V(G)$ and $e_{b_1},e_{b_2},..., e_{b_k}$ from $b$ to $u$, we just form some new cycle, and these edges lie on those new cycle. So non of these edges can be bridge, so $H$ contain no bridge. By induction, this statement is true.

Is my reasoning ok? I still feel a little bit awkward on $H$ contain no bridge part.

$\endgroup$
1
  • $\begingroup$ The induction does not hold: $H$ is not every graph with $n+2$ nodes and even degree.. $\endgroup$
    – Exodd
    Commented Sep 27, 2014 at 13:29

2 Answers 2

10
$\begingroup$

It's a little easier:

If $G$ contains a bridge, call $H$ one of the two subgraph in which the graph is divided by the bridge.

The sum of the degrees of all the nodes in $H$ is equal to 2 times the number of edges in $H$, so it's an even number. But all the nodes in it have even degree, except for the node from which the edge departed, that has odd degree, so we have an absurdity.

$\endgroup$
4
  • $\begingroup$ what is an even number? the sum of degree? the sum of degree is always even. You are trying to do a proof by contradiction? $\endgroup$ Commented Sep 27, 2014 at 17:26
  • $\begingroup$ exactly: the sum of the degree is always even, but if $G$ contains a bridge, then it can't be even $\endgroup$
    – Exodd
    Commented Sep 27, 2014 at 17:28
  • $\begingroup$ so you said, the node from which the edge departed, you mean the cut-vertex, and the cut vertex has to have odd degree? $\endgroup$ Commented Sep 27, 2014 at 17:34
  • $\begingroup$ I'm considering only one of the two parts of the graph you obtain deleting the bridge. In it every node has even degree, except for the cut vertex $\endgroup$
    – Exodd
    Commented Sep 27, 2014 at 17:36
1
$\begingroup$

I understand your Question Like this.

Consider a graph G(V,E) with all the vertices having even degree. Prove that the G would not have a bridge.

The reasoning is very simple. There is already a theorem stating "Every graph with all even degree vertices have an Eulerian circuit". This means that if the graph as you said contained a bridge then it means we will not have an Eulerian circuit contradicting the theorem stated above.

Hope I make sense.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .