Graph Run Time, Nodes and edges. 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.


*

*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.
 A: *

*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$.]

*(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.
A: 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.
