1
$\begingroup$

In an undirected connected simple graph G = (V, E), an edge e ∈ E is called a cut edge if G − e has at least two nonempty connected components. Prove: An edge e is a cut edge in G if and only if e does not belong to any simple circuit in G. This needs to be proved in each direction.

Typically I would write where I am for a problem like this, but I have no idea how to approach this proof, especially why it needs to be proved in each direction (what is the significance of this?). Any and all help would be much appreciated.

$\endgroup$
1
  • $\begingroup$ The question askes you to proof an equivalence, i.e. $\Leftrightarrow$. If you only proof one direction, e.g. $\Leftarrow$, then you have nothing said about the validity of $\Rightarrow$, hence you have to proof both to obtain equivalence. $\endgroup$ – M. Winter Aug 7 '17 at 9:24
2
$\begingroup$

Given a simple undirected connected graph $G = (V,E)$. Edge $e \in E$ is called a cut edge if $G^\prime = (V,E-\{e\})$ has at least two non-empty connected components.

Theorem. The edge $e \in E$ is a cut edge $\Leftrightarrow$ $e$ does not belong to a circuit in $G$.

$\Rightarrow$ Suppose $e \in E$ does belong to a circuit in $G$. Then, this circuit can be described as $e_1,\ldots,e_k$, with $e = e_i$ for some $1 \leqslant i \leqslant k$. Remove any $e_i$ in this circuit still allows the traversal $e_{i+1},\ldots,e_k,e_1,\ldots,e_{i-1}$, so $G$ is still connected, hence $e$ can not be a cut edge. Contradiction.

$\Leftarrow$ Suppose that after removing $e = \{v_1,v_2\}$ then $G$ is still connected. Then, consider the trail from $v_1$ to $v_2$. Adding $e$ to this trail creates a circuit (so there is a circuit in the original graph), hence a contradiction.

$\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.