1
$\begingroup$

Given a connected simple undirected Graph (V,E), in which deg(v) is even for all v in V, I am to prove that for all e in E (V,E\{e}) is a connected graph. Intuitively I would say that the given properties lead to a graph that consists of one or more connected circles, but I have no idea how I would go about proving that.

  • 0
    Damn - I didn't think it would be that simple. But yeah, now that you mention it... I just noticed we even have a Lemma with which this can be written even shorter. Thanks a lot, I really had a blockade on that one.2012-04-24

1 Answers 1

1

I don't think I could put it better than Daniel Fischer's comment:

In a connected graph, the sum of all the degrees of the vertices is even (each edge contributes two to the sum of the degrees). If the removal of an edge e disconnected the graph, the two components would both have an odd degree sum, because the degree of one vertex in each component were reduced by one.

But I might add some comments of my own:

  • The deletion of an edge can only break a connected graph $G$ into $2$ components (assuming deleting the edge disconnects the graph). Suppose edge $xy$ is deleted, and $v$ is a vertex. Then there is at least one path from $v$ to $x$ in $G$. If at least one of the paths does not path through $y$, then $v$ is connected to $x$ in $G \setminus \{xy\}$. Otherwise, paths from $v$ to $x$ all pass through $y$. So, $v$ is connected to $y$ in $G \setminus \{xy\}$.

  • The "sum of all the degrees of the vertices is even" is a consequence of the Handshaking Lemma, and is true whether or not the graph is connected.

  • For loop multigraphs (i.e., undirected graphs with loops and parallel edges)

    • Assuming loops contribute $2$ to the degree of a vertex, then the Handshaking Lemma and the above argument hold, and the claim is still true.
    • Assuming loops contribute $1$ to the degree of a vertex, then the result is false: for example, vertex set $\{1,2\}$, and edge set $\{11,12,22\}$.
  • The result is not true for infinite graphs: for example, vertex set $\mathbb{Z}$, and edge set $\{i(i+1):i \in \mathbb{Z}\}$.