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
    What about $K_n$? It satisfies these conditions.2012-10-07
  • 0
    @DouglasS.Stones The complete graph?2012-10-07
  • 0
    Does 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
  • 0
    Since 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
  • 0
    I'm sorry. I hadn't seen the previous message.2012-10-08

1 Answers 1