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

Question

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.

Answer 1

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