1
$\begingroup$

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.

  • 0
    I'm sorry. I hadn't seen the previous message.2012-10-08

1 Answers 1

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$.]]

  • 0
    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$.2012-10-11