edited by
640 views
1 votes
1 votes
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.
edited by

1 Answer

Best answer
3 votes
3 votes

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.
selected by

Related questions