# 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.

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.

-
are the graphs directed ? – Belgi Sep 22 '12 at 15:02

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.

-
i think i can grasp what you're saying, theres a vertex on a straight line graph such that if that vertex and its edges are removed it doesn't disconnect the graph G. so like, L-x-R => and the middle node(x) is removed? – AlanTuring Sep 22 '12 at 22:06
Almost exactly what I meant - note there can be several edges from $L$ to $x$ and several edges from $x$ to $R$, the key point is that when you are removing $x$ and the edges adjacent you can only disconnect $G$ if there are no edges between $L$ and $R$ since otherwise (since $R,L$ must be connected) $G$ would of been connected (and this would be a contradiction) – Belgi Sep 22 '12 at 22:19
i see thank you so much that makes sense. Could you elaborate a bit about the algorithm? How is it log(n)(n+m) particularly the log(n) part. – AlanTuring Sep 23 '12 at 3:33
For an m+n time do a DFS and take a leaf in any of the DFS trees – Belgi Sep 23 '12 at 11:48
So i think i figured it out using a O(m+n) algorithm. Basically, i am looking for a node in a connected graph G that when removed doesn't disconnect the graph. Using a BFS results in a tree(T) of graph G. This tree can be used in the sense that once a leaf of the tree is found, that node can be removed since it doesn't have any descendants and thus cannot disconnect the graph. This would be O(m+n) since the running time of BFS is O(n+m) and the only extra step would be actually removing the node which would just be another factor of n. – AlanTuring Sep 25 '12 at 21:00
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.

-