Graph Run Time, Nodes and edges.

Question

Hi i have these two problems that are part of a practice set i am doing for exams, i can't seem to get around them. If you can answer any of them thanks in advance.

1. For a given graph $G=(V,E)$ and an edge $e\in E$, design an $O(n+m)$-time algorithm to find, if it exists, the shortest cycle that contains $e$.

2. (a) Prove that every connected graph $G=(V,E)$ has a node $v\in V$ such that removing $v$ and all its adjacent edges will not disconnect $G$.

(b) For a given connected graph $G=(V,E)$, design an $O(n+m)$-time algorithm to find such a node.

Answer 1

For $2$: In order to prove$2.a$ we have to use the fact that the graph is finite (otherwise a graph that looks like a long string from both sides is a counterexample).

Proof is by induction on $|V|$ where the base case is clear (base is for $n=1,2$) .

Assume by negation that the claim is false, then for every $v\in V$ it holds that $G[V\backslash\{v\}]$ have exactly two connected components $L,R$ where both have $>0$ vertices in them and both are connected.

From the induction hypothesis we have a vertex in $L$ s.t removing it and all its adjacent edges will not disconnect $L$, since there is no edge from this vertex to a vertex in $R$ we have it that removing this vertex does not disconnect $G$.

To understand the proof I recommend to do a drawing of a vertex and the left and right side, do this again to the left side etc' untill the left side is too small to divide again in this manner .

For an algorithm: I can only think of a $O(log(n)(n+m))$ time algorithm doing what I wrote in the proof.

Answer 2

1. If the edge is $uv$, then finding a shortest cycle containing $uv$ is equivalent to finding a shortest path from $u$ to $v$ in $G \setminus uv$. This can be solved by taking breadth first traversal of $G \setminus uv$, starting at $u$, and ending if we hit the vertex $v$. This algorithm requires at most $O(\#\text{edges})$ steps.

   [Note: To actually give the cycle itself, a spanning tree will need to be stored in memory. To construct the cycle, we look at the parent node of $v$ in the tree, it's parent node, and so on, until we reach $u$. This path combined with the edge $uv$ is the shortest cycle in $G$ containing $uv$.]

2. (a) If $G$ is connected and non-empty, it has a non-empty spanning tree $T$. If we delete one of the leaf nodes in the spanning tree, $w$ say, then $G \setminus w$ is still connected (since $T \setminus w$ is connected).

   [Note: I'm assuming that you already have a proof that connected graphs have spanning trees.]

   (b) A spanning tree of $G$ can be constructed in $O(\#\text{edges})$ steps using breadth first search. The last node this algorithm adds to the spanning tree will be a leaf node of the spanning tree.