2
$\begingroup$

We need to show the following are equivalent:

(1) There exists an edge $e$ of $G$ such that $G−e$ is a tree

(2) $G$ is connected and the set of edges of $G$ which are not bridges form a cycle


This is what I tried:

$\Rightarrow$

We know a tree is a graph that is connected and has no cycles. So we have $G'=G-e$ is connected & acyclic. Now $G$ & $G'$ has $n$ vertices. We can prove $G'$ has $n-1$ vertices. Then for $G'$ it has $n$ vertices & $n-1$ edges. Then $G'$ is connected. How do I show if edges of $G$ which are not bridges form a cycles

Also, I have been able to show $(1) => G$ is connected with $V = E$. I know a result where this implies $G$ is connected & has exactly one cycle. (I have been able to prove it)

$\Leftarrow$

$G$ is connected and the set of edges of $G$ which are not bridges form a cycle. Does this mean $G$ is unicycle? As $G$ is connected by assumption & it forms a cycle.

$\endgroup$
0
$\begingroup$

$\Leftarrow$

All edges of $G$ that lie in a cycle are not bridges, because if you remove one of them you can still "take the other part of the cycle to get around". Therefore, $G$ has only one cycle $C$, and it contains all of the non-bridges. Removing any edge $e$ from $C$ now destroys the (only) cycle in $G$, which gives an acyclic graph. The resulting graph is also still connected because we removed a non-bridge. Therefore $G-e$ is a tree.

$\Rightarrow$

Removing an edge from a non-connected graph cannot make it connected. Therefore $G$ was connected. Since $G-e$ is connected, $e$ must have been part of a cycle in $G$. Since $G-e$ is a tree, all cycles of $G$ must go through $e$ (otherwise they would still be present in $G-e$).
Say $e=\{v,w\}$. There exists a unique path $P$ from $v$ to $w$ in $G-e$, since it is a tree. Every edge on $P$ is not a bridge of $G$, because they all lie on the cycle $P\cup e$. If there were more cycles in $G$, then there would be multiple paths from $v$ to $w$ in $G-e$, contradicting that it's a tree. Therefore $P \cup e$ contains all the non-bridges.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.