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.
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.