# Why graph $G = (V, E)$ is elementary cycle?

If graph $G = (V, E)$ is bi-connected, and $\forall$ pair $(u, v)$ $u, v \in V$, $(u, v) \notin E$ graph $G - u - v$ is disconnected $\Rightarrow$ graph $G$ is the elementary cycle.

-
What about $K_n$? It satisfies these conditions. – Douglas S. Stones Oct 7 '12 at 21:53
@DouglasS.Stones The complete graph? – brainail Oct 7 '12 at 22:00
Does disconnected mean, that it has more than one component? What is the elementary cycle? $C_n$? – draks ... Oct 7 '12 at 22:05
@jofisher: That's right; e.g. for e.g. $K_4$ the condition "for all pairs (u,v)..." is vacuously true. It might seem unimportant, but if one were to attempt to prove this result by induction, this would need to be accounted for. – Douglas S. Stones Oct 7 '12 at 22:15
@DouglasS.Stones Mm.. For ${K}_{4}$ it isn't true, because I can't remove any edge. Where is my mistake? – brainail Oct 8 '12 at 7:11

I'm going to assume you're trying to prove:

Theorem: Let $G=(V,E)$ be a simple biconnected graph on $n=|V|$ vertices where $n \geq 3$. If $G$ satisfies the property $P$: "for all distinct $u,v \in V$, if $uv \not\in E$ then $G \setminus \{u,v\}$ is disconnected", then $G=C_n$ or $G=K_n$.

Proof sketch (since this is tagged homework):

Base case: The theorem is true for $n=3$, by inspection.

Inductive step: Assume the theorem is true for $m$-vertex graphs, for $m \in \{3,4,\ldots,n-1\}$.

• If $G$ satisfies $P$ and $G \neq K_n$, then $G \setminus \{u,v\}$ is disconnected for some $u,v \in V$. Call the disconnected components $H_1,H_2,\ldots,H_t$. [[Need to show that $t=2$.]]

• Let $M_1$ and $M_2$ respectively be the subgraphs of $G$ induced by the vertices $V(H_1) \cup \{u,v\}$ and $V(H_2) \cup \{u,v\}$, together with the edge $uv$. Use the inductive hypothesis on $M_1$ and $M_2$ to show that $G=C_n$. [[Need to show (a) that both $M_1$ and $M_2$ have strictly less than $n$ vertices, (b) that $M_1$ and $M_2$ are also biconnected and satisfy $P$, (c) that, if $M_1$ or $M_2$ were complete graphs on $4$ or more vertices, then a contradiction arises, and (d) that $G=M_1 \cup M_2 \setminus \{uv\}$ is $C_n$.]]

-
At first look, I don't understand why $t = 2$.. – brainail Oct 9 '12 at 20:05
I don't want to spoil it for you, but, try drawing an example of biconnected graph $G$ in which the deletion of $u$ and $v$ gives rise to e.g. $t=3$ non-empty components. Then ask: does it satisfy $P$? – Douglas S. Stones Oct 9 '12 at 21:33
Ok, I see why $t = 2$ But I can't figure out why ${M}_{1}$ and ${M}_{2}$ are satisfy P.. – brainail Oct 11 '12 at 16:03
We know $M_2 \setminus \{uv\}$ is a connected subgraph of $G$ (otherwise $t>2$). So, if $M_1$ doesn't satisfy $P$, then neither does $G$. – Douglas S. Stones Oct 11 '12 at 21:34