1
$\begingroup$

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.

$\endgroup$
6
  • 1
    $\begingroup$ I don't see how the proof could be trivial for multigraphs if it is not for simple graphs. Simple graphs are special cases of multigraphs, so if it's true for multigraphs it is also true for simple graphs. $\endgroup$ Jun 3, 2020 at 17:30
  • $\begingroup$ In an undirected multigraph if there are two edges between a pair of vertices , or a loop you get a circuit right there $\endgroup$ Jun 3, 2020 at 17:35
  • $\begingroup$ But a multigraph does not need to have two edges between a pair of vertices, the only thing we know is that it is allowed. So a simple graph is a multigraph that happens not to have multiple edges between two vertices. $\endgroup$ Jun 3, 2020 at 17:38
  • $\begingroup$ If you say it like that then yes , it’s true and the proof only concerns simple graphs $\endgroup$ Jun 3, 2020 at 17:39
  • 1
    $\begingroup$ I don't know. It's not clear to me that you can always delete edges until every vertex has degree $2$. It seems easier to prove that if the graph has no cycles, then it is a tree and therefore has a vertex of degree $1$. $\endgroup$ Jun 3, 2020 at 18:18

1 Answer 1

1
$\begingroup$

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

enter image description here

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

$\endgroup$
1
  • $\begingroup$ Thx for the solution , especially regarding the deletion of the vertex processes , it is elegant . I had already seen the longest path method you described above and just thought of an another solution and wanted to check it . $\endgroup$ Jun 4, 2020 at 3:24

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.