Talk:Eulerian path

From Wikipedia, the free encyclopedia

WikiProject Mathematics
Mathematics Portal
This article is within the scope of WikiProject Mathematics, which collaborates on articles related to mathematics.
Mathematics rating: Start Class Mid Priority  Field: Discrete mathematics

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)

Contents

[edit] 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)

[edit] 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)

[edit] 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)

[edit] Pentagram

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

[edit] image?

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

[edit] 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)

[edit] '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)

[edit] 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

[edit] 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)

[edit] 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 Pn 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)