The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+1 vote

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.

  1. Given a good graph, devise a linear time algorithm to find two such vertices.
asked in Graph Theory by Veteran (116k points) | 99 views

1 Answer

+2 votes
Best answer

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.
answered by Loyal (9.5k points)
selected by

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,434 questions
53,630 answers
70,898 users