Take the 2-minute tour ×
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.

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|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? –  jofisher 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? –  jofisher Oct 8 '12 at 7:11
show 3 more comments

1 Answer 1

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|improve this answer
    
At first look, I don't understand why $t = 2$.. –  jofisher 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.. –  jofisher 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
add comment

Your Answer

 
discard

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.