Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I was hoping someone could help me understand this graph theorem better.

Theorem: Adding an edge from any graph G either joins two components of G or adds a cycle to G, but not both.

Especially this tidbit:

Proof: Let G be an arbitrary graph, let e = {u, v} be any edge that is not in G, and let G" = (V, E ∪ {e}).

• If u and v are in different components of G, those two components are joined in G" . If any cycle in G" contains edge e, then it contains another path from u to v, all of whose edges are in G, which is impossible. Thus, no cycle in G" contains edge e. It follows that every cycle in G" is also a cycle in G.

u and v are different vertices, and G'' is the graph of G but with one extra edge right? It says I can't create a cycle, but isn't this graph picture a counter example? The circles are vertexes. I'm guessing I'm misunderstanding the proof. Thanks for the help.

share|improve this question
    
It says that adding the extra edge can't create a cycle if $u$ and $v$ are in different components of $G$. –  Chris Eagle Oct 27 '12 at 7:40

2 Answers 2

up vote 0 down vote accepted

Perhaps it would be more intuitive for you if we restated the theorem in an equivalent form.

Theorem: Every edge of a graph is either a bridge (a bridge joins two disconnected components) or it is a part of a cycle.

Proof: Given any edge $e=(u,\ v)$, either there is a path from $u$ to $v$ not through $e$, or there isn't.

In the former case, let a path be $P = (u,\ w_1,\ \cdots,\ w_k,\ v)$ where $w_i$ are intermediate vertices. Then we have a cycle $C = (u,\ w_1,\ \cdots,\ w_k,\ v,\ u)$ which contains $e$.

If there is no path from $u$ to $v$ except $e$ then removing $e$ disconnects $u$ and $v$ so that $e$ is a bridge connecting two disconnected components. $\square$

To see how your theorem implies this one, take any edge of a graph and remove it. Then adding the edge back and applying your result, we have that the original edge either joins to components (is a bridge) or creates a cycle (is a part of a cycle).

Your picture does not contradict the theorem. The edge you add creates a cycle but does not join two disconnected components.

share|improve this answer

The first line of that tidbit requires u and v to be in different components; in your example, there is only one component, so that part of the proof does not apply. Take a look at Wikipedia for a definition of a component.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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