No Eulerian walk in a graph, and how to fix it

725 Views Asked by At

Explain why a simple graph $G=(V,E)$ has no Eulerian walk, where the vertices are $V =\{a,b,c,d,e,f\}$ and the edges are $E=\{ab,ae,af,be,cd,ce,cf,df\}$.

Show that it is possible to add one edge to $G$ to obtain a simple graph still, that does have an Eulerian walk, and find such a walk. There may be more than one way to do this; identify all ways to add the edge.

When working out this question, I found out that vertices $a,c,e$ and $f$ have odd degrees of 3. But a graph cannot have more than 2 vertices of odd degree to have a Eulerian path, so $G$ doesn't have an Eulerian path.

That is all that I have come up with and I am not sure how to approach the second question.

1

There are 1 best solutions below

2
On BEST ANSWER

When approaching graph theory problems dealing with a specific graph, drawing always helps:

The graph

Since you have already shown that no Eulerian walk exists in the graph, I will concentrate on how to add an edge to this graph so that it does have an Eulerian walk.

Adding one edge to the graph flips the parities of the vertices it connects – odd to even, even to odd. We have four odd vertices and we need two, so we should add an edge between two vertices of odd degree; those vertices are $a,c,e,f$ and have a black spot in my drawing, so we would have six edges to choose from. However, to keep the graph simple we cannot add an edge between two vertices that are already connected by an edge; this whittles down the possible edges to $ac$ and $ef$.

Here are possible Eulerian paths for both augmented graphs.
$+ac:$ fcdfaceabe
$+ef:$ afeabecdfc