Prove that connected graph $G$ with $\delta (G)\geq 3$ contains a cycle $C$ such that $G-E(C)$ is still connected.

Question

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 attempt is not correct.

Answer 1

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

Answer 2

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.