# an O(m+n) algorithm to decide whether a graph can be reduced to a single edge with two vertices

Given B and C operations.

• B-operation: When two multi-edges connect a pair of vertices, replace the multi-edges with a single edge connecting the pair of vertices.

• C-operation: When one edge connects vertices $$u$$ and $$v$$, another edge connects $$v$$ and $$w$$ (where $$u \ne w$$), and there is no other edge incident to $$v$$, remove the vertex $$v$$, and replace the two edges with a new edge connecting $$u$$ and $$w$$.

Input a graph with n vertices and m edges, and check whether it can be reduced to a single edge with two vertices. How to make the algorithm be $$O(m+n)$$ time complexity?

My thought is to record the deg of vertices. But can't figure out what to do next.

• An idea: I believe that for a normal undirected graph (without multiedges!) not being reduced to a line graph is equivalent to one node having degree $\geq 3$. There is a simple $O(m+n)$ algorithm that removes all multiedges from a graph. Apr 17, 2022 at 19:19
• @plshelp. Consider the graph with edges AB, BE, AC, CE, AD, DE. Apr 18, 2022 at 8:29

#### The Simple Idea

Keep the graph without multi-edges by B-operations. Apply C-operation whenever we can, keeping track of possible new opportunities of C-operations in a set of vertices.

#### A Simple Algorithm

Assume there is no loops in the graph.

1. Replace all edges between the same pair of vertices by one edge.
There will be at most $$m$$ edges left. The graph is a simple graph now.
2. Put all vertices in a set $$S$$.
3. Repeat the following routine until $$S$$ is empty.
1. Poll $$S$$ to get a vertex $$v$$.
2. If the degree of $$v$$ is 2,
1. apply the C-operation that removes $$v$$ together with two edges incident to $$v$$ and adds an edge between vertex $$u$$ and $$w$$. If there has been another edge between $$u$$ and $$w$$, merge these two edges by a B-operation, so that the graph remains a simple graph.
2. add $$u$$ and $$w$$ to $$S$$.
4. Return "Yes" if the graph is a single edge with two vertices. Otherwise, return "No".

#### Time-Complexity Analysis

Each execution of step 3.2.1 will reduce the number of edges in the graph at least by 1. Hence step 3.2.1 can be executed at most $$m$$ times. That means step 3.2.2 can be executed at most $$m$$ times, too.

Hence, the number of times a vertex is added to $$S$$ by step 3.2.2 is at most $$2m$$. Since $$S$$ contains $$n$$ vertices initially, the total number of times that a vertex is added to $$S$$ is $$n+2m$$. So the total number of times the removal of a vertex from $$S$$ can be done by step 3.1 is at most $$n+2m$$. That is, step 3.1 can be executed at most $$n+2m$$ times.

Hence the running time of step 3 is $$O(n+m)$$. The running time of step 1 and step 2 is $$O(n+m)$$. So, the time-complexity of the algorithm is $$O(n+m)$$.