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.
Why graph $G = (V, E)$ is elementary cycle?
-
0What about $K_n$? It satisfies these conditions. – 2012-10-07
-
0@DouglasS.Stones The complete graph? – 2012-10-07
-
0Does disconnected mean, that it has more than one component? What is **the** elementary cycle? $C_n$? – 2012-10-07
-
0@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. – 2012-10-07
-
0@DouglasS.Stones Mm.. For ${K}_{4}$ it isn't true, because I can't remove any edge. Where is my mistake? – 2012-10-08
-
0@draks Yep, ${C}_{n}$ – 2012-10-08
-
0Since there's no non-edges in $K_4$, the property is [vacuously true](http://en.wikipedia.org/wiki/Vacuous_truth). Note: there's also no non-edges in $C_3=K_3$. – 2012-10-08
-
0I'm sorry. I hadn't seen the previous message. – 2012-10-08
1 Answers
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$.]]
-
0At first look, I don't understand why $t = 2$.. – 2012-10-09
-
0I 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$? – 2012-10-09
-
0Ok, I see why $t = 2$ But I can't figure out why ${M}_{1}$ and ${M}_{2}$ are satisfy P.. – 2012-10-11
-
0We 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$. – 2012-10-11