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$

1 Answer 1

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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .