Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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$.]]

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.