Math 2.0

Combinatorics Theorem

Degrees along an Eulerian trail

Builds on Degree of a vertexEulerian trail

Statement

Let GG be a finite graph, and let WW be an Eulerian trail of GG from uu to vv. If u=vu = v, then every vertex of GG has even degree. If u≠vu \neq v, then uu and vv have odd degree and every other vertex has even degree.

Remarks

Proof idea: each time WW passes through a vertex, it uses two edges at that vertex. Only the start and the end use one edge without a partner. Thus a graph with an Eulerian trail has 00 or 22 vertices of odd degree. The Seven Bridges of Königsberg have 44.

Reading path

To understand this page from the ground up, read these 7 pages in order. The foundations come first.

Show the path as a graph
Graph, definition, no evidence levelGraphdefinitionNeighbourhood, definition, no evidence levelNeighbourhooddefinitionWalk, definition, no evidence levelWalkdefinitionDegree of a vertex, definition, no evidence levelDegree of a vertexdefinitionTrail, definition, no evidence levelTraildefinitionEulerian trail, definition, no evidence levelEulerian traildefinitionDegrees along an Eulerian trail, statement, no evidence levelDegrees along an Eule…statement
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Graph definition
  2. Neighbourhood definition
  3. Walk definition
  4. Degree of a vertex definition
  5. Trail definition
  6. Eulerian trail definition
  7. Degrees along an Eulerian trail statement

Further reading

  1. Web https://en.wikipedia.org/wiki/Eulerian_path, Properties
About this page
Tag0CDVDGWGEG
URIm2://0CDVDGWGEG
Kindstatement, theorem
WritingW0 stub
MSC05C45
StatusThis copy of the site has no build data. Run m2 status 0CDVDGWGEG.
UsesDegree of a vertex, Eulerian trail

Markdown · JSON · Edit on GitHub

What this page needs for W1

  • an inventory row: the row of the inventory that the node accounts for (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

No page links to this page yet.