1
$\begingroup$

I was going the text "Discrete Mathematics and its Application" by Kenneth Rosen where I came across the algorithm for finding out the Euler Circuit in a graph in which all vertices have even degree. Now before they stated their algorithm they gave a brief discussion of the idea and I felt like including it as it might help in understanding my question better.

The Discussion

Constructing an Euler Circuit in G.

Suppose that $G$ is a connected multigraph and the degree of every vertex of $G$ is even. We will form a simple circuit that begins at an arbitrary vertex $a$ of $G$. Let $x_0 = a$. First, we arbitrarily choose an edge $\{x_0, x_1\}$ incident with $a$. We continue by building a simple path $\{x_0, x_1\}, \{x_1, x_2\}, ...,\{x_{n-1}, x_n\}$ that is as long as possible. For instance, in the graph $G$ in Figure we begin at $a$ and choose in succession the edges $\{a, f\},\{f, c\},\{c, b\},\{b, a\}$.

The path terminates since the graph has a finite number of edges. It begins at $a$ with an edge of the form $\{a, x\}$, and it terminates at $a$ with an edge of the form $\{y, a\}$. This follows because each time the path goes through a vertex with even degree, it uses only one edge to enter this vertex, so that at least one edge remains for the path to leave the vertex. This path may use all the edges, or it may not.

An Euler circuit has been constructed if all the edges have been used. Otherwise, consider the subgraph $H$ obtained from $G$ by deleting the edges already used and vertices that are not incident with any remaining edges. When we delete the circuit $a,f,c,b,a$ from the graph in Figure, we obtain the subgraph labeled as $H$.

Since $G$ is connected, $H$ has at least one vertex in common with the circuit that has been deleted. Let $w$ be such a vertex. (In our example, $c$ is the vertex.)

Every vertex in $H$ has even degree (because in $G$ all vertices had even degree, and for each vertex, pairs of edges incident with this vertex have been deleted to form $H$). Note that $H$ may not be connected. Beginning at $w$, construct a simple path in $H$ by choosing edges as long as possible, as was done in $G$. This path must terminate at $w$. For instance, in Figure, $c, d, e, c$ is a path in $H$. Next, form a circuit in $G$ by splicing the circuit in $H$ with the original circuit in $G$ (this can be done since $w$ is one of the vertices in this circuit). When this is done in the graph in Figure, we obtain the circuit $a, b, c, d, e, c, b,a$.

Continue this process until all edges have been used. (The process must terminate since there are only a finite number of edges in the graph.) This produces an Euler circuit.

The discussion which they had is quite clear and I have no problem with it. The problem is in the line in bold just before the algorithm where they talk about not going into the possible removal of ambiguity by nicely specifying the steps of the algorithm, (they say that the ambiguity might arise due to the arbitrary choosing of circuits in the discussion above) but don't give some example of the situation of the possible ambiguity.

Algorithm gives the constructive procedure for finding Euler circuits given in the discussion preceding. (Since the circuits in the procedure are chosen arbitrarily, there is some ambiguity. We will not bother to remove this ambiguity by specifying the steps of the procedure more precisely.)

ALGORITHM: Constructing Euler Circuits


procedure Euler(G: connected multigraph with all vertices of even degree) 
    circuit :=  a circuit in G beginning at an arbitrarily chosen vertex 
                with edges successively added to form a path that returns
                to this vertex 
    H := G with the edges of this circuit removed while H has edges 
    begin 
        subcircuit :=   a circuit in H beginning at a vertex in H that 
                        also is an endpoint of an edge of circuit 
        H := H with edges of subcircuit and all isolated vertices removed 
        circuit := circuit with subcircuit inserted at the appropriate vertex 
    end {circuit is an Euler circuit}
    

I just want to know what sort of ambiguity( with a possible example) they are talking about which gets removed if we follow the nicely written algorithm.

$\endgroup$
1
  • 1
    $\begingroup$ He says, "We arbitrarily remove an edge ...". There's the ambiguity. To remove it, assume the edges are listed in some order, and select the first edge in the list that satisfies the condition. $\endgroup$
    – saulspatz
    Jun 8 '20 at 19:19
2
$\begingroup$

The "ambiguity" in the example above is in choosing where to go when you get to node c, after eliminating the first "cycle": you could go $c-d-e$ or you could go $c-e-d$. If the degree of $c$ was, say, $50$, then you'd have 48 choices (just at $c$, not to mention at other vertices you'd encounter later).

Of course, there's also ambiguity in choosing a starting vertex (removed if the starting vertex is an argument to the algorithm), and which edge to traverse starting at the starting vertex. If the "first edge, directed" is a parameter of the algorithm, then the ambiguity consists of "as I reach each vertex, which as-yet-unused edge leaving that vertex do I choose?"

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