Adding and removing Edges to Graph 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. 
 A: 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.
A: 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.
