Talk:Eulerian path

Error in article

From Discrete Mathematics, 4th Ed., by Dossey, Otto, Spence, and Vanden Eynden: Thm 3.5: "Suppose a multigraph G is connected. Then G has an Euler circuit iff every vertex has even degree. Furthermore, G has an Euler path iff every vertex has even degree except for two distinct vertices, which have odd degree. When this is the case, the Euler path starts at one and ends at the other of these two vertices of odd degree." Is this contradicting the article? I can't tell, and I don't want to edit it, being a mere CS major and not an expert in mathematics. --Aciel 02:05, 7 May 2005 (UTC)

I do not see how this is contradicting the article. Can you give a more detailed explanation what you refer to ? MathMartin 17:08, 7 May 2005 (UTC)

I also don't understand what point is being made, but I'll note that the quoted theorem from Dossey et al is wrong. To have an Euler path, one needs at most two vertices of odd degree, not exactly two. --Zero 03:46, 8 May 2005 (UTC)

In response to the first question, I think you may be confusing Euler paths and circuits. In response to this last comment, well it depends how you define euler paths, just like how you define natural numbers. For example, the starting and ending vertices can be defined to be distinct, as in "Discrete Mathematics" Third Edition, by Susanny S. Epp. Also an Euler path/circuit can be defined to be a graph/subgraph or a sequence.

For reference, the above mentioned definition: "Let G be a graph, and let v and w be two distinct vertices of G. An Euler path from v to w is a sequence of adjacent edges and vertices that starts at v, ends at w, passes through every vertex of G at least once, and traverses every edge of G exactly once."

124.177.66.44 (talk) 10:30, 29 January 2008 (UTC)

Edge Disjunct?

The article makes a reference to edge disjunct cycle graphs, but neither this article, nor the cycle graphs one that it links to, define edge disjunct. Eythian 05:52, August 11, 2005 (UTC)

Missing def

"diconnected" is linked to the glossary but not in the glossary. I assume it means something along the lines of "strongly connected". Deco 05:56, 30 August 2005 (UTC)

I'll change it to just "connected", since any type of connectivity implies strong connectivity when the in-degree and out-degree are equal at every vertex. (Proof: if the digraph is connected but not strongly connected, there is a strong component that has edges coming in but no edges coming out. Now count the heads and tails of edges inside that strong component to find a contradiction.) --Zero 11:14, 30 August 2005 (UTC)

Pentagram

Is a pentagram a unicursal star? --South Philly 03:39, 11 July 2006 (UTC)

image?

Why is an uneulerian path the only picture here?--Josh Rocchio 01:15, 29 September 2006 (UTC)

Missing proof of Euler Tour

I'm missing a proof which proofs that if G a connected graph with an Euler tour if and only if every vertex of V(G) has an even degree. Is it somewhere else on the wiki? Otherwise I'd like to give one. --Noud 15:57, 29 July 2007 (UTC)

I came to this article to find a proof, but unfortunately there is none. Please give yours! Thanks, --Abdull (talk) 09:17, 16 July 2008 (UTC)

'path'

This article says "an Eulerian path is a path (graph theory)", and the path article says that 'path' normally means a 'simple path', but an Eulerian path does not have to be a simple path, does it? Perhaps some mention should be made of this. Can someone confirm this? ssepp^(talk) 08:47, 15 September 2007 (UTC)

The term "path" in graph theory and in computer science has contradictory meanings. Computer scientists seem to mean any trail (no repeated vertices; there may be repeated edges) or walk (any vertices or edges may be repeated). In graph theory a path must have no repeated vertices or edges. I will revise the article when I can to remove the unfortunate ambiguity of the word "path". Zaslav (talk) 04:21, 27 April 2010 (UTC)

From Glossary of graph theory#Walks:

• "A walk is an alternating sequence of vertices and edges."
• "A trail is a walk in which all the edges are distinct."
• "Traditionally, a path referred to what is now usually known as an open walk. Nowadays, when stated without any qualification, a path is usually understood to be simple, meaning that no vertices (and thus no edges) are repeated."

I often see "path" used when "walk" would be more accurate, but it's not wrong to use "path" to mean "an alternating sequence of vertices/edges". Justin W Smith ^talk/_stalk 05:54, 28 April 2010 (UTC)

If this POV statement you quote is correct, "traditionally" must refer to 50 years ago. In graph theory, that's a long time! Why would we use 50-year-old obsolete terminology?

I don't understand how you can say "often see path"! I don't. Please provide citations. I've read a lot of graph theory. "Path" is wrong if you're following the general usage in graph theory. If you agree "path" is wrong, why are you reverting? It makes no sense. Please give a better explanation. Zaslav (talk) 16:46, 28 April 2010 (UTC)

Are you claiming that this article should be renamed "Eulerian trail"? If we strictly define "path" to only mean "simple path", then the article would need to be renamed as such. Justin W Smith ^talk/_stalk 18:33, 28 April 2010 (UTC)

Yes, I am! But I'm not going to spend any more time on it. Zaslav (talk) 16:36, 29 April 2010 (UTC)

Strictly speaking "Eulerian paths" are not "paths" because they are not simple. Out of curiosity I just did a search for "Eulerian path" in articles since 2000 on google scholar and got over 400 hits. As I said before, I'm ok with using "path" in a more general sense (i.e., to mean a non-necessarily-simple walk). Justin W Smith ^talk/_stalk 18:40, 28 April 2010 (UTC)

@Zaslav: You said, "I don't. Please provide citations." Here you go...

For comparison (results restricted to papers since 2000):

• "eulerian path" gets 425 hits,
• "eulerian cycle" gets 327,
• "eulerian circuit", gets 246,
• "eulerian trail" gets 170, and
• "eulerian walk" gets 69.

It appears "eulerian path" and "eulerian cycle" are the most commonly used terms, and Wikipedia should reflect that. Justin W Smith ^talk/_stalk 18:47, 28 April 2010 (UTC)

Well, thanks for doing the research. A few remarks: My feeling is that the results partially reflect carelessness in terminology, which makes sense because most people even in math and computer science are not very careful. If you were to make the search more thorough, you would ask about "euler path/trail"; I wonder what you'd find. I also wonder how many of these "path" and "cycle" usages are in computer science, where those terms seem to be used indiscriminately for walks, trails, or paths in the graph-theory sense. Also, I don't think the frequencies of "cycle" vs. "circuit" are that different; I would give some weight to correctness/consistency of terminology, not only frequency of usage. (When one term is rare, it's a different matter.) Also, while checking all kinds of terminology, there's "eulerian/euler tour", tour = circuit = closed trail. But seriously, we've spent enough time on it. Thanks again for the data. Zaslav (talk) 16:46, 29 April 2010 (UTC)

At MathSciNet, "eulerian trail" beats "eulerian path" 54 to 33. In my experience, many graph theorists who call it "eulerian path" would never otherwise use the word "path" for a self-intersecting walk, in other words they don't think an eulerian path is a path. Zero^talk 17:07, 29 April 2010 (UTC)

That sounds exactly right to me. Did you also check "euler path/trail/walk"? Zaslav (talk) 21:44, 1 May 2010 (UTC)

I did it again using "euler" as well as "eulerian", plus plurals: cycle 39, tour 106, circuit 69, path 62, walk 16, trail 83. Zero^talk 05:17, 2 May 2010 (UTC)

Thanks again! That's tour (106), circuit (69), cycle (39) for closed, and trail (83), path (62) for open, with walk (16) ambiguous. I'm surprised at how many say tour. No one term is totally dominant. "Path" is not favored. Zaslav (talk) 15:23, 2 May 2010 (UTC)

John Dwyer paper on Eulerian circuits

I've reverted the latest edit, which referenced http://www.algana.co.uk/Research/Circuits.pdf by John Dwyer. This paper is not a peer-reviewed publication and contains no proofs. Equation 34 of this paper, which claims to have a closed formula for the number of Eulerian circuits in a complete graph on n vertices, gives values for K5 and K7 appear to contradict those given in the paper "Asymptotic Enumeration of Eulerian Circuits in the Complete Graph" by McKay and Robinson. —Preceding unsigned comment added by Myasuda (talk • contribs) 15:30, April 6, 2008

Error in source code

The link to C++ source code http://tuxv.blogspot.com/2007/05/eulerian-path.html should be removed since the source code is, beside a number of bugs, incorrect. It generates a path (or cycle) which visits each edge *at most* once and not *exactly* once, thus it is simply *not* Eulerian. —Preceding unsigned comment added by 58.186.123.121 (talk) 18:20, 29 May 2008 (UTC)

Semi-Eulerian

I added a mention of semi-Eulerian, because that's a not uncommon term used, but we should also have an example for that. While P_n of course works, perhaps something that's also simple, but slightly more interesting like Image:Semi-Eulerian graph.png would be good. Unfortunately I don't know of any easy programs to label that more nicely and make it look like the other two images in the article. Can somebody help out? - Taxman ^Talk 14:15, 31 May 2008 (UTC)

self-intersecting path

Please define self-intersecting path. Thanks, --Abdull (talk) 09:17, 16 July 2008 (UTC)

WTH is a Even Degree?

WTH is a Even Degree? —Preceding unsigned comment added by 193.136.166.125 (talk) 20:28, 6 April 2009 (UTC)

As I understand evenness and oddness is determined by counting the number of edges associated with a given vertex. For a vertex to be even it must have an equal number of "incoming" and "outgoing" edges. Odd vertices do not, which is why there cannot be more than two for the graph to be Eulerian.

Should this be explained somewhere in the article?Reaster (talk) 16:27, 10 August 2009 (UTC)

Faster algorithm than Fleury

Isn't there a faster recursive O(edges+vertices) algorithm than Fleury? I can't remember the name, but it was like start at any vertice (if we are finding a eulerian path, start at a vertice of odd degree), if the vertice has degree 0, add it to the circuit and return, else for each neighbour, delete the edge between the vertice and the neighbour and recurse on the neighbour. Rand0m011 (talk) 22:48, 18 April 2009 (UTC)

I'm sure it can be done in O(#edges) time but we need to find a reference. McKay (talk) 06:51, 19 April 2009 (UTC)

I may be a bit late, but I was just looking into this today and yes, here is a link [1]. Fleury's algorithm seems impractical because you have to check for bridges at each step. That cycle finding algorithm is cool but kind of sneaky. Is is something we want in the article? Alejandro Erickson (talk) 18:44, 4 June 2010 (UTC)

The "algorithm" at that link is wrong and useless. But we need a linear time alg for this page. Zero^talk 10:10, 5 June 2010 (UTC)

Commentary in the article

The following commentary on the article was at the end of the introduction. I've moved it here to discuss. WRONG! A graph made by starting from an Eulerian graph and adding any number of isolated vertices is not connected but still Eulerian!

This is correct... but rather pedantic. Perhaps it could be discussed later in the article? —Preceding unsigned comment added by 76.29.6.37 (talk) 00:15, 28 January 2010 (UTC)

Pedantic, is it? Well don't let me get in the way of amateur academicians happily editing away at anything mathematical in sight, totally unconcerned with such arcane notions as rigor. You will actually find that the article already has a correct exposition further down, where it says something to the effect of connected simple graphs will be Eulerian if and only if all their vertices have even degree. Quite different from what is presented in the 'helpful' introductory paragraph, isn't it? Unless you find arguing over such minute differences already exhausts your monthly allowance of 'pedantism'. —Preceding unsigned comment added by 83.132.117.74 (talk) 00:31, 28 January 2010 (UTC)

Well, given that the sentence in question starts with "In 1873, Carl Hierholzer published the first complete characterization", we have to check what he (Carl Hierholzer) actually proved... --Martynas Patasius (talk) 21:52, 28 January 2010 (UTC)

Obviously, he (Carl Hierholzer) did not prove anything as previously stated in the introductory paragraph, since you cannot prove a falsehood. (And it is immediately obvious, i think, that what was previously asserted was false; in fact, the correct statement actually appeared further down the article.) The interesting aspect to all this is that when some imbecile originally wrote the introduction, no one cared or even noticed that it was wrong; but as soon as you point it out it, somehow it becomes paramount to make sure we're not incurring in 'Original Research'... Wikipedia has become a bureaucratic joke. —Preceding unsigned comment added by 83.132.234.45 (talk) 22:09, 28 January 2010 (UTC)

Well, I wouldn't say it is as obviously false, as you seem to think. The statement "further down the article" doesn't seem to be incompatible with either version. Also, let's take an example - a graph with several vertices and no edges. Is it an Eulerian graph? Does it have an Eulerian cycle? Well, does a graph having no cycle have an Eulerian cycle? If we word the question like this, the answer seems to be "No.". On the other hand, if we take your definition, then the graph in question would be an Eulerian graph, as it has no vertex with an odd degree... I am not going to claim that this example obviously disproves anything, but I guess it should prove that a source wouldn't hurt... --Martynas Patasius (talk) 22:31, 28 January 2010 (UTC)

But you misunderstand: What i said is that if you take a (conventional, ie, connected) Eulerian graph and then add isolated vertices, you still have an Eulerian graph. That has no bearing on whether an edgeless graph is itself an Eulerian graph (since if you start from a conventional Eulerian graph, you'll already have edges in it). But, to answer your question directly, yes, i consider an edgeless graph to be an Eulerian graph, just as it is customary to say that (for instance) the empty set is a closed set (in the topological sense), but also an open set, since it trivially verifies the properties needed in both cases.

So, I found a random article (C. ST J. A. Nash-Williams, "Connected Detachments of Graphs and Generalized Euler Trails", J. London Math. Soc. s2-31: 17-29, [2]) that defines the "Eulerian graph" as both connected and having no vertices of odd degree... Of course, it doesn't prove anything by itself, but at least it shows that the falsity of the statement in question is not "immediately obvious"... --Martynas Patasius (talk) 22:48, 28 January 2010 (UTC)

Precisely, the article defines; it doesn't prove. That is, at any point, you're free to say that you only allow a graph to be Eulerian if it is also connected (which is reasonable, since the unconnected variants are uninteresting). The previous introduction to the Wikipedia article, however, claimed that someone (Hierholzer) had proved that Eulerian graphs were connected, when, using the definition of Eulerian graph previously offered by the article, this isn't true: The definition in the introduction didn't require Eulerian graphs to be connected. If you allow unconnected Eulerian graphs, these will, in fact, exist. Now, if you know your way around graphs, that little confusion is harmless; you'll always know what the other person is referring to. But in an encyclopedia, this is a grave error. It might induce someone to think that Eulerian implies connectedness, as, for example, a graph being complete actually implies connectedness.

Ah, finally - a source that shows your version might be considered to be generally accepted - Weisstein, Eric W. "Eulerian Graph." From MathWorld--A Wolfram Web Resource. [3] (why didn't I look at it from the beginning..?). Although, of course, it would still be nice if someone who understands German better than I do would check if the Hierholzer's article (C. Hierholzer "Über die Möglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechung zu umfahren" Mathematische Annalen VI (1873), 30–32. [4]) uses the same definition as this (Wikipedia's) article. Actually, it seems to be at least somewhat different: looks like he considered graphs with "keiner oder zwei ungerade Knottenpunkte" (none or two vertices with odd degrees?), thus the note in this (Wikipedia's) article ("The first complete characterization of connected graphs that have an Eulerian circuit was published in 1873 by Carl Hierholzer, [...]") seems to be inexact (looks like he considered the graphs with Eulerian cycle or Eulerian path)... --Martynas Patasius (talk) 01:01, 29 January 2010 (UTC)

Don't rely on this MathWorld article - it's quite messy. E.g., it talks about connected Eulerian graphs and shows illustration of non-connected ones. And the definition given there works only for connected graphs. I've already reported these problems to MathWorld's team. Maxal (talk) 01:56, 29 January 2010 (UTC)

O( | V | + | E | ) complexity

So, how does the cycle finding algorithm have a O(n + m) time complexity? It does

3          pick an incident vertex v and remove (u,v) from E

|E| times. If the graph is represented with a linked list removing each edge costs O(|E|). If it's represented with a matrix removing an edge costs O(1), but picking an incident vertex costs O(|V|). So step 3 costs O(|E|) with a linked list graph, and it has to be done |E| times, so the time complexity can't be smaller than O(|E| ^ 2). If it's with a matrix it can't cost less than O(|E| * |V|). What am I missing something here? Is there a quick way to delete an edge that I don't know? Shinra.Electric.Power.Company (talk) 22:12, 29 May 2011 (UTC)

With an adjacency list structure, the while loop can be executed in constant time per incident edge plus constant overhead. This is not entirely trivial because of the requirement to "delete" each edge, which means that when (u,v) is deleted, (v,u) must be deleted too (I assume we are working on a undirected graph). Simply marking the edge as deleted in a standard adjacency list structure won't do since the call find_tour(u) can be made many times for a single vertex u and we don't want to have to skip over the deleted edge multiple times. One solution is to represent the adjacency lists as doubly-linked lists, since these allow a node to be deleted in constant time when the position of the node is known. This is also more tricky than it looks because the while loop has to be implemented in a way that doesn't break when recursive calls delete nodes from the list being scanned. The constant time overhead per call to find_tour() adds up to O(|E|+1) altogether since there is at most |E|+1 calls. So the total cost is O(|E|+1). The V is not required since the algorithm only scans one component of the graph. Some people would simplify O(|E|+1) to O(|E|) but I don't think that is correct. McKay (talk) 01:02, 30 May 2011 (UTC)

I don't understand exactly your method of deleting an edge in constant time, but it doesn't matter; the algorithm can definitely be done in O(|E|) (or O(|E|+1)) in other ways I didn't think before (using pointers to booleans for the edges and always picking the first edge in the list so you only go through the list once and it doesn't become a problem if some edges are marked). Shinra.Electric.Power.Company (talk) 01:07, 1 June 2011 (UTC)

See Doubly linked list#Removing a node for node deletion. Marking edges does not suffice because the whole list of neighbours is scanned multiple times for each vertex. There is not just a single call to find_tour(u) for each vertex u like there is for other algorithms like depth-first search. There can be many calls to find_tour(u) for the same vertex u active even at the same time, because the recursion follows a path in the graph that can repeatedly intersect itself. It is required for a good running time that the total for all the scans of the neighbours of u be proportional to the degree of u. So when one of the scans deletes an edge, the other scans must not see it at all even just to skip it. McKay (talk) 02:04, 1 June 2011 (UTC)

Pronunciation

Does anyone know who made Fleury's algorithm?24.123.191.50 15:58, 16 November 2006 (UTC)

someone hook up the pronounciationAshwinr 14:31, 9 August 2006 (UTC)

    Sounds like oiler, but I don't know how to link pronunciations 144.13.15.245 15:36, 21 September 2007 (UTC)

Unicursal redirects to here. There should be an explanation of how unicursality (?) relates to an Eulerian path so that the link doesn't seem confusing. moink 14:54, 11 Apr 2004 (UTC)

Strange question I suddenly got curious about

If, in a connected undirectional graph, all vertices are of degree 4, does there necessarily exist an Eulerian path with the additional criterion that every vertex is visited once before any are revisited? 2.25.121.100 (talk) 17:48, 22 June 2011 (UTC)

No. An easy counterexample is three vertices in a triangle, each also having a loop connecting it to itself. 213.249.135.36 (talk) 19:27, 26 June 2011 (UTC)

Connected?

I notice the definition given does not state the graph must be connected. Discrete Mathematics by Richard Johnsonbaugh states that it must. Thoughts? What does your reference book say?Handsofftibet (talk) 12:06, 23 August 2011 (UTC)

Who cares whether the text says it or not, it's true: the graph must be connected. —David Eppstein (talk) 16:03, 23 August 2011 (UTC)

There are obviously (trivial examples of) graphs that satisfy the definition given in this article that aren't connected, so maybe you can rephrase your response so it's a little more helpful? Cheers, Ben (talk) 11:30, 24 August 2011 (UTC)

Oh, ok. graphs, in general, need not be connected. In order to be Eulerian, a graph must not only have even degree, but also be connected. I thought this question was referring to textbooks that made the mistake of leaving out the connectivity condition, but maybe I'm misreading? —David Eppstein (talk) 16:04, 24 August 2011 (UTC)

Ok, I think you're right and there is some confusion, so allow me to be careful for a minute. From the introduction:

The term Eulerian graph has two common meanings in graph theory. One meaning is a graph with a Eulerian circuit, and the other is a graph with every vertex of even degree. These definitions coincide for connected graphs.

This infers that your connectedness requirement isn't universal, otherwise why not just say that these two definitions are equivalent? So, it's easy to see that the two definitions are not equivalent for disconnected graphs. Now given the definition of an Euler cycle in this article:

In graph theory, an Eulerian trail is a trail in a graph which visits every edge exactly once. Similarly, an Eulerian circuit or Eulerian cycle is a Eulerian trail which starts and ends on the same vertex.

we see that in the disconnected case the sets of graphs satisfying either of the two definitions aren't disjoint either: consider the graph with two vertices and a single loop - it clearly satisfies both definitions. However, according to Johnsonbaugh:

In honor of Euler, a cycle in a graph G that includes all of the edges and all of the vertices of G is called an Euler Cycle.

In which case, my example graph fails to have an Euler cycle. It is, however, Eulerian according to (at least on of) the definitions in this article, but not Eulerian according to your connectedness requirement.

I think the point is: this is all a big mess. We're going to have get some things down very explicitly in this article or readers aren't going to have a hope. If you agree with that, then maybe we can start to put forward some suggestions on how best to do that. Cheers, Ben (talk) 22:50, 24 August 2011 (UTC)

Ok, I see what you mean: the necessary condition isn't connectivity, it's a weaker condition that involves connectivity only of the nonzero-degree vertices. I've corrected the "properties" section of the article to take this into account. I think the rest is still ok because it generally does not try to provide strict "if and only if" characterizations, only sufficient conditions. —David Eppstein (talk) 23:50, 24 August 2011 (UTC)

The text reflects the fact that some sources use "Eulerian" or "Euler" to mean "all degrees are even" rather than "has an Eulerian circuit". There is an example cited, and it cites two others. I see this reasonably often, especially in enumeration papers. McKay (talk) 03:11, 25 August 2011 (UTC)

Graph-Magics' Algorithm

I'm not sure that the Graph-Magics website would count as a reliable source, but it provides a very simple algorithm to find an Eulerian path. It's equivalent to Hierholzer's algorithm, but it's easier to understand and implement:

1. Start with an empty stack and an empty circuit (eulerian path).

- If all vertices have even degree - choose any of them.

- If there are exactly 2 vertices having an odd degree - choose one of them.

- Otherwise no euler circuit or path exists.

2. If current vertex has no neighbors - add it to circuit, remove the last vertex from the stack and set it as the current one. Otherwise (in case it has neighbors) - add the vertex to the stack, take any of its neighbors, remove the edge between selected neighbor and that vertex, and set that neighbor as the current vertex.

3. Repeat step 2 until the current vertex has no more neighbors and the stack is empty.

It also provides a similar algorithm for a directed graph.

I also observe that if the top-of-stack (TOS) element can be accessed without popping it, the algorithm can be written as:

1. Push the starting vertex onto the stack.

2. If the TOS has no remaining edges, pop the vertex, and add it to the path. Otherwise, remove one of the edges, and push the vertex to which it connected.

3 Repeat step 2 until the stack is empty.

From this it follows that the sum of the number of vertices on the current stack and the path equals the number of removed edges plus one, which of course never exceeds the total number of edges plus one. Hence, the same memory can be used for the stack and the path by building them in opposite directions. (The same is also true of the original version of the algorithm, but is harder to see with all the pops and pushes.)

---

The Graph Magics algorithm is Hierholzer's algorithm with the following twist: instead of using any arbitrary already-encountered vertex with unused edges, it always uses the last one. This simplifies merging the sub-tour into the complete tour. All the vertices at the end of the current tour that have no remaining edges can be removed and put aside, and the new tour can then be appended to the end of the remaining current tour.

The following is equivalent, and is an algorithm that's very easily understood and implemented:

For a connected, undirected graph with zero or two odd-degree vertices:

1. Allocate a memory buffer to store vertices in the path (represented as pointers or array indices) with its size equal to the number of edges plus one. Treat it as two initially-empty (last-in-first-out) lists: a head list, which starts at the beginning of the buffer and is built forward, and a tail list, which starts at the end of the buffer and is built backwards.

2. Add the starting vertex for the path to the the head list. If there are odd-degree vertices, use one of them; otherwise, use any vertex.

3. If the last vertex in the head list has no remaining edges, remove it from the head list, and add it to the tail list; otherwise, remove one of the remaining edges and add the vertex to which it connected to the head list.

4. Repeat step 3 until all the edges have been removed (or equivalently, until the head and tail lists meet). This can be determined by simply decrementing a count of the remaining edges each time an edge is removed.

5. Upon completion, the buffer will contain an Eulerian path.

If the number of edges isn't known, then the algorithm can be run until all vertices have been moved from the head list to the tail list, provided of course that the buffer is at least as large as the number of edges plus one. The tail list will then contain a Eulerian path. When run in this way, the algorithm is essentially identical to the original Graph-Magics algorithm. The only real difference is that the tail list is built backwards, so the original direction of the path is maintained.

Thinkatron (talk) 23:07, 9 August 2020 (UTC)

Does "Eulerian graph" actually have two common meanings?

The article claims: "The term Eulerian graph has two common meanings in graph theory. One meaning is a graph with an Eulerian circuit, and the other is a graph with every vertex of even degree. These definitions coincide for connected graphs." However, it cites as evidence a paper called "Two-graphs, switching classes and Euler graphs are equal in number." That paper provides the definition:

DEFINITION 3. An Euler graph ([7], [11, p. 20]) is a graph in which every node has even degree.

It doesn't call a graph with all even-degree vertices an Eulerian graph; it calls an Euler graph. Perhaps such a graph commonly goes by both terms and the paper just used one of them; or perhaps the term Euler graph was chosen because Eulerian graph was already taken for graphs with an Eulerian circuit. In any case, unless a reference is provided calling even-vertex graphs Eulerian graph, I think the statement should be removed.

---

Wolfram MathWorld has this to say under Euler graph:

The term "Euler graph" is sometimes used to denote a graph for which all vertices are of even degree (e.g., Seshu and Reed 1961). Note that this definition is different from that of an Eulerian graph, though the two are sometimes used interchangeably and are the same for connected graphs.

Though the "sometimes used interchangeably" phrase gives some support the the notion that Eulerain graph can have both meanings, the main takeaway is that a Eulrian graph differs from an Euler graph, and the even the term Euler graph is not widely used for all-even-vertices graphs (i.e., "sometimes used to denote..."). So I don't think it's accurate to state that Eulerian graph has two common meanings unless there's evidence that the definition that doesn't require an Eulerian circuit exist (because the graph is connected) is actually in common use. Thinkatron (talk) 05:19, 19 August 2020 (UTC)

References

I have definitely seen both meanings of "Eulerian graph", and don't remember ever seeing "Euler graph". In Google Scholar, "Euler graph" is used about 1/4 as often as "Eulerian graph", and without noticeably different meaning (except that it is also used for other things: the multigraphs of crossings and arcs of Euler diagrams, and something algebraic related to Eulerian numbers; don't ask me why Euler graphs go with Eulerian numbers and not Eulerian graphs or Euler numbers but that's what this paper says). I think the Euler tour definition of Eulerian graphs is more common, and easily sourced to standard textbooks. See e.g. Diestel, "Graph Theory" (2005 internet edition), p. 21 and Bondy and Murth "Graph Theory with Applications", p. 51.

But it is also easy to find old and new research papers that, when convenient, define Eulerian to mean even degree, regardless of connectivity: e.g., On the number of Eulerian orientations of a graph, M Mihail, P Winkler, Algorithmica, 1996; Cycles containing all the odd-degree vertices, K Cameron, C Thomassen, Journal of Combinatorial Theory, Series B, 2020.

I think it would be a mistake to try to invent a distinction between the two terms "Euler graph" and "Eulerian graph" that is not supported in the literature, or to pretend that both meanings are not commonly used. I think it is also generally a mistake to rely on MathWorld for terminological issues. —David Eppstein (talk) 05:37, 19 August 2020 (UTC)

I wasn't suggesting a distinction be made between an Eulerian graph and an Euler graph. I was suggesting that the article not claim that the second meaning of Eulerian graph is common unless it is actually common. I expect that the term Euler graph is, as you say, quite widely used to refer to graphs with Eulerian cycles. What I doubt is that the opposite is common. A regular Google search for "Eulerian graph" finds very many examples of the term referring to graphs with Eulerian cycles, very few (besides Wikipedia) referring to possibly-unconnected graphs with all-even-degree vertices. (I didn't see any, but I didn't look at every single one). It is obviously used that way on occasion, as your two examples show, but does that mean it's common? I doubt it is, though I haven't done anything like a extensive search of the literature, so I could be mistaken. In any event, the cited reference should at least directly support the claim, which the current one doesn't. (Though I realize many papers, such as the two mentioned, are paywalled.) — Preceding unsigned comment added by Thinkatron (talk • contribs) 07:05, 19 August 2020 (UTC)