Proof check : In a connected simple undirected graph with degree of each vertex greater than $1$ there exists a cycle

Question

Question : Let $G\left( V,E\right) $ be a connected simple undirected graph such that $deg\left( v\right) \geq 2\forall v\in V$ , then there exists a simple circuit in $G$

We start by removing edges and forming sub-graphs . From every vertex $v$ of $G$ randomly delete edges of $v$ such that $\deg \left( v\right) =2\\. $ .

After removing the edges we get $G_{1},G_{2},G_{3}\ldots ,G_{n}$ connected components

Each connected component has three or more vertices , each of degree 2 since our original graph $G$ is a simple graph.

Thus each connected component has an Euler circuit , this Euler circuit becomes a simple circuit in our large graph $G$ with all edges replaced.

Answer 1

You cannot delete edges in the way you want. Consider the graph below:

This graph (the complete bipartite graph $K_{2,3}$) has two vertices of degree $3$ and three vertices of degree $2$. You cannot reduce any of the degree-$3$ vertices to degree $2$, because then one of the degree-$2$ vertices would end up having degree $1$ or $0$.

---

The standard approach to this problem is to find a cycle greedily: starting at any vertex, take a walk around the graph until you visit some vertex for the second time - revisiting that vertex creates a cycle.

---

You could also refine the edge-deletion approach you've currently got. But this will be more complicated.

First, whenever you have an edge between two vertices of degree $\ge 3$, delete it. When this ends, every edge has an endpoint of degree $2$. If all vertices have degree $2$, then your argument works. If not, take a vertex $v$ of degree $\ge 3$ and follow edges from $v$ until we reach a vertex of degree $\ge 3$. It is either

• the same vertex $v$, in which case we get a cycle;
• another vertex $w$ of degree $\ge 3$, in which case we can delete the entire $v,w$-path we found (and the vertices on it) and again end up at a subgraph with minimum degree $2$.

Repeat this until we find a cycle or until all our remaining vertices have degree exactly $2$.