3
$\begingroup$

For this to occur, every vertex has to have an even degree. Since this is a connected graph, we know that this must be true.

How do you prove that the closed walk visits every edge exactly twice? Does the existences of a closed walk mean that there is a cycle in the graph?

$\endgroup$
  • 3
    $\begingroup$ Not all connected graphs have vertices of even degree only. For example, $K_4$. $\endgroup$ – Frpzzd May 1 '17 at 23:58
  • $\begingroup$ Will this require two separate cases - one Eulerian and one non-Eulerian? $\endgroup$ – Payal Ahuja May 2 '17 at 0:04
  • 1
    $\begingroup$ The graph with every edge doubled does have even degree at each vertex, so it has an Eulerian cycle. $\endgroup$ – Daniel Schepler May 2 '17 at 0:04
  • $\begingroup$ Could you please explain what it means to "double" each edge? $\endgroup$ – Payal Ahuja May 2 '17 at 0:05
  • $\begingroup$ It means you form the graph with the same set of vertices, but for each edge in the original graph you put in two edges in the new graph, connecting the same pair of vertices. $\endgroup$ – Daniel Schepler May 2 '17 at 0:10
1
$\begingroup$

@Daniel Schepler gives an excellent answer in the comment above. Here is a constructive proof.

If a graph is connected it contains a spanning tree. On that spanning tree, you can find a walk that visits each edge exactly twice: draw the spanning tree as a planar graph and walk around it always keeping an edge on your right.

Each tree-edge is visited exactly twice.enter image description here

Now add the missing edges one by one. Each time you add an edge, use it to add a detour (back and forth) to the walk.

Each non-tree-edge is visited exactly twice.enter image description here

$\endgroup$
  • $\begingroup$ (+1) what you are doing is essentially a 'spanning tree' of the edges. I don't know what this is called. Also, another way of thinking about it is you split a vertex into two (each edges then goes to one vertex or the other), and repeat this until you get a tree. $\endgroup$ – 6005 May 2 '17 at 4:53
  • $\begingroup$ Note you actually proved a stronger statement than in the question: there exists a path that walks every edge exactly twice in opposite directions (which does not follow easily from the Eulerian cycle argument). $\endgroup$ – Marc van Leeuwen May 2 '17 at 10:32
1
$\begingroup$

Proof by induction on the size (number of edges) of the (finite) connected graph $G.$

Let $G$ be a connected graph of size $m.$ Assume that every connected graph of size less than $m$ has a closed walk that traverses each edge twice. If $m=0$ then $G$ consists of a single vertex and the trivial walk does the job. Suppose $m\gt0.$ Choose an edge $uv$ of $G.$

Case 1. $G-uv$ is connected.

By the inductive hypothesis, $G-uv$ has a closed walk $W$ that traverses each edge twice. Start at $u;$ walk on $uv$ from $u$ to $v;$ follow the closed walk $W,$ beginning and ending at $v;$ walk back to $u$ on the edge $uv.$

Case 2. $G-uv$ is disconnected.

Let $H_u$ be the component of $G-uv$ containing $u,$ and let $H_v$ be the component containing $v.$ By the inductive hypothesis, $H_u$ has a walk $W_u$ that traverses each edge twie, and $H_v$ has a walk $W_v$ that traverses each edge twice. Start at $u;$ follow the walk $W_u$ from $u$ back to $u;$ walk on $uv$ from $u$ to $v;$ follow $H_v$ from $v$ back to $v;$ return to $u$ on the edge $uv.$

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