1
$\begingroup$

I tried to prove this statement by contradiction, where G is a connected graph in which each vertex has even degree and G has a cut edge, then proceed letting x, y, z to be in G where x, y are endpoints to the cut edge e. So x and y are in two separate component of G - e. Then I tried to show that there is a path from x to z and one from y to z, so x and y must not be in two components. Therefore there is a contradiction. But I don't know if the proof is valid and how to best utilize the fact that the vertices have even degrees?

$\endgroup$
1
  • 1
    $\begingroup$ How did you show that there is a path from x to z and a path from y to z? This doesn't immediately sound easy? The easiest way (IMO) to prove this result is to observe that x and y each have odd degree once e is deleted. Then if x and y are in the same component, contradiction e was not a cut edge, whereas if x and y are in different components, then the degree sum of each component is odd, contradiction by handshake lemma. $\endgroup$ Commented Dec 20, 2021 at 3:59

2 Answers 2

1
$\begingroup$

HINT: if there is a cut edge $e$, then each of the 2 components of $G\setminus \{e\}$ has exactly $1$ vertex of odd degree. The Handshake Lemma has something to say about this though.

$\endgroup$
0
$\begingroup$

Let's take an arbitrary edge $e$ and study whether it's a cut edge. We will take its end points $v, w$, and see if there is a path from one to the other that doesn't use $e$.

The graph has an Eulerian cycle. Take such a cycle that starts at $v$. Either this cycle gets to $w$ before it traverses $e$, or its reverse does. Either way, deleting $e$ does not disconnect the graph.

$\endgroup$

You must log in to answer this question.

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