1
$\begingroup$

Let $G$ be a 3-connected graph. Prove that for every three vertices $a, b, c$ of $G$ there exists a cycle in $G$ that contains $a,b$ but not $c$.

Here is my work. Since $G$ is a 3-connected graph, the minimum edges need to be removed in order to make it become disconnected is $3$. The degree of very vertex must be at least $3$. If we remove edge $ac$ and $bc$ if they exist, it's still connected. Then, by removing the other edges that connected to $c$, the graph is still connect. Since the degree of vertices $a$ and $b$ are at least 2, there must be a cycle contains $a$ and $b$.

Is it correct?

$\endgroup$
  • 1
    $\begingroup$ The first part of your argument is more or less correct. However, note that when someone says $k$-connected, they generally mean vertex connectivity. Since edge connectivity is always greater than or equal to vertex connectivity, your argument still holds, but I just want to make sure that you are aware of the difference. $\endgroup$ – EuYu May 15 '14 at 5:16
  • $\begingroup$ The latter part of your argument is incorrect (or at least confusing). First, what do you mean by "removing the other edges that connected to $c$, the graph is still connect"? If you remove all edges connected to $c$, the graph is clearly disconnected (i.e. $c$ is disconnected from the graph). Also, "since the degree of vertices $a$ and $b$ are at least $2$, there must be a cycle containing $a$ and $b$", this statement is not true. $\endgroup$ – EuYu May 15 '14 at 5:17
  • $\begingroup$ "by removing the other edges that connected to c, the graph is still connect" I mean without the vertex $c$. I know "since the degree of vertices a and b are at least 2, there must be a cycle containing a and b" is not true. Can I say since the degree of every vertex except $c$ is at least $2$, there must be a cycle contains $a$ and $b$? $\endgroup$ – user137988 May 15 '14 at 7:02
  • $\begingroup$ You are getting on the right track but you don't seem to be quite there yet. It's indeed true that removing $c$ leaves the graph connected with minimum degree at least $2$. But knowing that the minimum degree is $2$ is not sufficient to say that there exists a cycle containing $a$ and $b$. You need something a bit stronger than that. Here's a hint: What is the connectivity of the graph after removing $c$? $\endgroup$ – EuYu May 15 '14 at 7:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.