CMI2011-B-02b

Question

Let $G$ be a connected graph. For a vertex $x$ of $G$ we denote by $G−x$ the graph formed by removing $x$ and all edges incident on $x$ from $G$. $G$ is said to be good if there are at least two distinct vertices $x, y$ in $G$ such that both $G − x$ and $G − y$ are connected.

Given a good graph, devise a linear time algorithm to find two such vertices.

Answer 1

Suppose $p$ be an maximal path in the graph $G.$

Let $u$ and $v$ be its end points.

Since p is the maximal path in the graph $G$ all the neighbours of $u$ and $v$ will be on the path $p.$

So, if we remove either $u$ or $v$ from the path $p$ then the neighbours of $u$ or the neighbours of $v$ remain connected through the path $p.$

Hence, after removing $u$ or $v$ from $G$ the graph $G$ remains connected.

Now, in the question we are told to give an algorithm to find the points $u$ and $v.$

The algorithm is given below

• STEP 1: Start
• STEP 2: Find a maximal path $p$ in the graph $G.$ (This would take $O(n)$ time.)
• STEP 3: The endpoints of that path are our required answer.
• STEP 4: STOP.

Comments

can you specify the algorithm to find the maximal path of a graph?

---

STEP 1: Pick any vertex(v)  in the graph and join it with any neighbouring vertex (u) of (v). Let the path uv be $p'$.

STEP 2: We extend $p'$ by joining the endpoints of $p'$ by its neighbouring vertices. We rename the new extended path as $p'$

STEP 3: We stop when we find a cycle or there does not exist any neighbouring vertices of the end points. Otherwise repeat steps 2 and 3.