Adding and removing Edges to Graph

Question

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.

Answer 1

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.

Answer 2

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.