13
$\begingroup$

In a connected simple graph every vertex has a degree at least $3$. Prove that the graph contains a cycle such that the graph remains connected when the edges of this cycle are deleted.

Source: https://www.komal.hu/verseny/2000-02/mat.e.shtml

I've tried this: Pull out of $G$ a cycle $C$ with smallest perimeter $p$.

Claim: No two nonconsecutive vertices in the circle $C$ are adjacent (else we could make smaller cycle then we already have).

Let $C_1,C_2,...,C_k$ be all components in $G-C$ and I want to prove $k=1$.

If $n_i = |V(C_i)|$ and $e_i= |E(C_i)|$, then we have $$e_i = {3n_i\over 2}-b_i$$ where $b_i$ is a number of edges between $C_i$ and $C$. Because $G$ is connected we have $b_i\geq 1$ for each $i$. Because of the claim we have: $$b_1+b_2+\cdots +b_k = p$$

I have no idea what to do now.

Edit: As Misha Lavrov pointed in a comment, this attemt is not correct.

$\endgroup$
6
  • 4
    $\begingroup$ You're assuming that the graph is $3$-regular, while we're only given that it has minimum degree $3$. Also, taking a minimum-length cycle is not always sufficient. This graph, for example, has $10$ cycles of length $3$, only $8$ of which leave the graph connected when removed. You could even use this method to find an example where none of the minimum-length cycles work. $\endgroup$ – Misha Lavrov Feb 3 at 15:57
  • $\begingroup$ Yes but, can we say that is true if $G$ is 3 regular? @MishaLavrov $\endgroup$ – Aqua Feb 4 at 15:48
  • $\begingroup$ Not sure. The one bit of partial progress that's easy to point out is that this holds for graphs with at least $2n-1$ edges: set aside a spanning tree to ensure connectedness, and you still have $n$ edges left, which contain a cycle. $\endgroup$ – Misha Lavrov Feb 4 at 17:01
  • $\begingroup$ Is there a counterexample for non-simple graphs? $\endgroup$ – bof Feb 5 at 2:33
  • $\begingroup$ I don't know how to solve the problem, so I don't know if this is a helpful hint or not. If the statement is true, then it remains true under the weaker assumption, that there is at most one vertex of degree less than $3$. In trying to prove this more general statement by induction, it may help to know that a minimal counterexample must be $2$-connected. $\endgroup$ – bof Feb 5 at 2:37
3
$\begingroup$

Suppose $G$ to be a counterexample with a minimal number of edges.

$G$ has no isthmus $vw$.

Otherwise, contract edge $vw$ and consider a cycle $C$ of the reduced graph whose removal does not disconnect the reduced graph. Then $C$ is entirely within one of the components of $G$ produced by deleting $vw$ and so deleting it from $G$ does not disconnect $G$ and there is no counterexample after all.

No two adjacent points $v,w$ of $G$ can both have degree at least $4$.

Otherwise simply remove edge $vw$.

$G$ has no triangle $u,v,w$.

Otherwise, removing edges $uv,vw,wu$ must disconnect the graph. Without loss of generality we can assume that $u$ is then in a separate component from $v$ and $w$.

If $\rho (u)=3$, then let $x\in N(u)/\{v,w\}$. Then $xu$ is an isthmus.

So $\rho (u)>3$ and therefore $\rho (v)=\rho (w)=3$.

If $(N(v)\bigcap N(w))/\{u\}=\{ y\}$, then contracting all edges joining vertices in $\{u,v,w,y\}$ produces a simple connected graph with all vertices of degree at least $3$ and we can proceed using minimality as in the 'isthmus' proof.

Otherwise, we can assume $N(v)=\{ u,w,y\}$ and $N(w)=\{ u,v,z\}$ with $y\ne z$. Then contracting all edges joining vertices in $\{u,v,w\}$ produces a simple connected graph with all vertices of degree at least $3$ and we can again proceed using minimality.

G is 3-regular

Otherwise let $N(u)=\{x,y,v\}$ with $\rho (v)>3$. Reduce $G$ by removing $u$ and adding edge $xy$. The new graph has a cycle $C$ whose removal does not disconnect the graph. If $xy$ is in this cycle then replace it by $xuy$. Removing the possibly amended cycle $C$ does not disconnect $G$.

Proof

Let $N(u)=\{v,a,b\}$ and $N(v)=\{u,c,d\}$ . Delete $u$ and $v$ and add in edges $ab$ and $cd$. The new graph has a cycle $C$ whose removal does not disconnect the graph.

If neither $ab$ nor $cd$ is in $C$ then removing $C$ does not disconnect $G$.

If, say, $ab$ but not $cd$ is in $C$ then replace it in the cycle by $aub$. Removing the possibly amended cycle $C$ does not disconnect $G$ and again there is no counterexample.

Finally suppose both $ab$ and $cd$ are in $C$. Part of $C$ is a path from $a$ to say $c$ (or to $d$) which does not include $ab$ or $cd$. Combining this path with $auvc$ then gives a cycle which can be removed without disconnecting $C$.

$\endgroup$
9
  • $\begingroup$ One question here though: If say $uv$ is in $C$ but $vw$ is not in $C$, then how do you know $G \setminus E(C')$ is connected, where $C' \doteq C -\{uv\}+\{uxv\}$? What if edge $wv$ is a cut-edge in the new graph minus the edges in $C$? $\endgroup$ – Mike Feb 6 at 19:57
  • $\begingroup$ By assumption the removal of C does not disconnect and the only change we have then made is to replace $uv$ by $ux,xv$. The edge $vw$ is not in $C'$ and so is not going to be deleted. $\endgroup$ – S. Dolan Feb 6 at 20:06
  • 1
    $\begingroup$ Yes I see the first part of that. But the edge $vw$ is not in $G$ either though. $\endgroup$ – Mike Feb 6 at 20:08
  • $\begingroup$ I see the point you're making now. The fact that $xw$ cannot be an isthmus might help circumvent the issue but it needs some thought. Thanks for pointing that out -I'll get back to you on that. $\endgroup$ – S. Dolan Feb 6 at 20:39
  • 1
    $\begingroup$ I only am aware of this because I got stuck on it too! Meanwhile I do admire how cleanly you make your points above, I am still working on being able to write that crisply. $\endgroup$ – Mike Feb 6 at 20:43
2
$\begingroup$

NOTE (2/6/2021): This answer was posted today and is a redo from the one posted on Wednesday. I came up with this independently of S. Dolan.

Proof SKETCH: Let $G$ be the graph on $n$ vertices where every vertex has degree at least 3. We assume that every simple graph of minimum degree 3 and on at most $n-1$ vertices, has a cycle such that the graph remains connected even after removing the edges of the cycle.

Case A: $G$ has at least one triangle $T$. Let $T$ be a triangle in $G$. Let us write $T=y_1y_2y_3$.

Subcase A.1: $G \setminus E(T)$ has 2 components with $y_1 \in C_1$ and $y_2,y_3 \in C_2$.

A.1.1 If there is only one vertex $w_2 \in C_2$ that is adjacent to either $y_2$ or $y_3$, AND there is only one vertex $w_1 \in C_1$:

A.1.1.1 If $w_2$ has 2 neighbors in $C_2 \setminus \{y_2,y_3\}$ then add the edge $w_1w_2$ and remove vertices $y_1,y_2,y_3$ Then the resulting graph $G'_{n-1}$ is simple and has minimum degree 3. Also, a cycle $C'_{n-1}$ in $G'_{n-1}$ so that $G'_{n-1} \setminus E(C'_{n-1})$ is connected, translates naturally to a cycle $C_{n}$ in $G$ so that $G\setminus E(C_n)$ is connected.

A.1.1.2 If $w_2$ has only one neighbor $w'_2$ in $C_2 \setminus \{y_2,y_3\}$ then add the edge $w_1w'_2$ and remove vertices $y_1,y_2,y_3,w_2$. Then the resulting graph $G'_{n-1}$ is simple and has minimum degree 3. Also, a cycle $C'_{n-1}$ in $G'_{n-1}$ so that $G'_{n-1} \setminus E(C'_{n-1})$ is connected, translates naturally to a cycle $C_{n}$ in $G$ so that $G\setminus E(C_n)$ is connected.

A.1.2 If there is either more than one vertex in $C_2$ adjacent to either $y_2$ or $y_3$ or there is more than one vertex in $C_1$ adjacent to $w_1$ collapse $T$ into a vertex $v_T$ and add the edges $v_Tw$; $w \not \in T$; $w$ adjacent in $G$ to a vertex in $T$. Then the resulting graph $G'_{n-1}$ is simple and has minimum degree 3. Also, a cycle $C'_{n-1}$ in $G'_{n-1}$ so that $G'_{n-1} \setminus E(C'_{n-1})$ is connected, translates naturally to a cycle $C_{n}$ in $G$ so that $G\setminus E(C_n)$ is connected.

Subcase A.2: $G \setminus E(T)$ has 3 components. Collapse $T$ into a vertex $v_T$ and add the edges $v_Tw$; $w \not \in T$; $w$ adjacent in $G$ to a vertex in $T$. Call the resulting graph $G'_{n-1}$. Then the resulting graph $G'_{n-1}$ is simple and has minimum degree 3. Also, a cycle $C'_{n-1}$ in $G'_{n-1}$ so that $G'_{n-1} \setminus E(C'_{n-1})$ is connected, translates naturally to a cycle $C_{n}$ in $G$ so that $G\setminus E(C_n)$ is connected.

Subcase A.3: $G \setminus E(T)$ has one component. Then we would be done as here we have a cycle namely $T$ so that $G \setminus E(T)$ is connected.

Case B: $G$ has no triangles. If $G$ has no triangles, then pick a vertex $v_n$ and write $G_{n-1} \doteq G \setminus \{v_n\}$, and write $u_1,u_2,\ldots, u_k$ as the neighbors of $v_n$ in $G$. Add to $G_{n-1}$ a matching $M$ of $\lfloor \frac{k}{2} \rfloor$ edges between the $u_i$s.

(C) If there remains [at most] 1 vertex $u_3$ of degree 2 in the resulting graph, then contract $u_3$ to an edge $e_{u_3}$ and call the resulting graph $G'_{n-1}$. As $G$ is triangle free the resulting $G'_{n-1}$ is simple. Let $C'_{n-1}$ be a cycle so that $G'_{n-1}\setminus E(C'_{n-1})$ is connected.

We consider 2 possibilities:

Subcase B.1: $C'_{n-1}$ contains 2 or more arcs in $M$. Then let $u_1$ and $u_2$ be such that (i) $u_1$ and $u_2$ are incident to distinct edges in $M \cap C'$, and (ii) there is a path $P'_{n-1}$ from $u_1$ to $u_2$ in $C'_{n-1}$ that contains no arcs in $M$ and does not contain $e_{u_3}$. One can observe that there exists such a $P'_{n-1}$. Then let $C_n=vu_1P'_{n-1}u_2v$. Then $G \setminus E(C_n)$ is connected. [Indeed let us suppose that there is a vertex $u_3$ as in (C) above. Then let $u$ and $w$ be any 2 vertices in $V(G) \setminus \{u_3,v_n\}$, and let $P'_{uw}$ be a path in $G'_{n-1} \setminus E(C'_{n-1})$. Then if $P'_{uw}$ contains any arcs $u_ju_{j+1}$ in $M$ or $e_{u_3}$ then as $M$ is a matching $\{u_j,u_{j+1}\} \cap \{u_1,u_2\}$ is empty. So replace $u_ju_{j+1}$ with $u_jv_nu_{j+1}$ and $e_{u_3}$ with $xu_3y$ where $xy \doteq e_{u_3}$ and so the resulting walk $W_{uw}$ is in $G \setminus E(C_n)$ so $u$ and $w$ are connected to each other in $G \setminus E(C_n)$ for each $u,w \in V(G) \setminus \{u_3,v_n\}$. If $P'_{uw}$ does not contain any arc in $M$ or $e_{u_3}$ then $P'_{uw}$ is in $G \setminus E(C_n)$ and so $u$ and $w$ are connected to each other for each in $G \setminus E(C_n)$ for each $u,w \in V(G) \setminus \{u_3,v_n\}$. But then as $e_{u_3} \not \in P'_{n-1}$ it follows that $xe_{u_3}y$ is in $G \setminus E(C_n)$ so $u_3$ is in the same component as
every other vertex in $V(G) \setminus \{u_3,v_n\}$, and as $v_n$ has degree 3, there is an edge in $G \setminus E(C_n)$ between $v_n$ and another vertex, so $v_n$ is in this component as well. And so $G \setminus E(C_n)$ indeed has only 1 component. ]

Subcase B.2: $C'_{n-1}$ contains exactly 1 arc $e=u_1u_2$ in $M$ and $e_{u_3}$ as in (C) above exists and is in $C'_{n-1}$ as well. Then write $e_{u_3} \doteq xy$; $x$ and $y$ the endpoints of $e_{u_3}$ in $G'_{n-1}$; so that the path $P'_{n-1}=xx_2x_3 \ldots x_lu_1$ in $C'_{n-1}$ contains neither $u_2$ nor $y$. Then let $P_n=u_3xx_2x_3 \ldots x_lu_1$ and let $C_n=v_nu_3xx_2 \ldots x_lu_1v_n$. Then $G \setminus E(C_n)$ is connected. [Indeed let $u$ and $w$ be any 2 vertices in $V(G) \setminus \{u_3,v_n\}$, and let $P'_{uw}$ be a path in $G'_{n-1} \setminus E(C'_{n-1})$. Then if $P'_{uw}$ contains any arcs $u_ju_{j+1}$ in $M$ then $\{u_j,u_{j+1}\} \cap \{u_1,u_2\}$ is empty [as $u_1u_2$ is in $C'_{n-1}$ so it cannot be in $P'_{uw}$ and also $u_1u_2 \in M$ a matching], so replace with $u_jv_nu_{j-1}$ and so the resulting walk $W'_{uw}$ is in $G \setminus E(C_n)$ so $u$ and $w$ are connected to each other in $G \setminus E(C_n)$ for all $V(G) \setminus \{u_3,v_n\}$. But then the edge $v_nu_2$ is in $G \setminus E(C_n)$, and so is the edge $u_3y$.]

The remaining cases are easier and won't be covered here.

$\endgroup$
1
  • $\begingroup$ You have edited this answer more than 40 times since it was posted. Every time you edit your answer, it bumps the question to the front page, and draws attention away from other questions. Please try to figure out precisely what it is you intend to say, post that answer, and leave it alone as much as possible. If you are writing something complicated, you can test things out in the Sandbox. $\endgroup$ – Xander Henderson Feb 7 at 15:02

Your Answer

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

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