Math 2.0

statement theorem

Euler's theorem on Eulerian circuits

Statement

Let GG be a finite connected graph or multigraph with at least one edge. Then GG has an Eulerian circuit if and only if every vertex of GG has even degree.

Remarks

The condition is necessary by the theorem on degrees along an Eulerian trail. A consequence: a finite connected graph has an Eulerian trail that is not closed if and only if exactly two vertices have odd degree. Hierholzer's algorithm builds an Eulerian circuit: it joins closed trails until every edge is used.

History

Leonhard Euler showed the necessity of the condition, and he stated without proof that it is sufficient. The first complete proof is by Carl Hierholzer. It was published after his death, in 1873.

Explanations

L1 human

You can draw a connected graph in one closed stroke exactly when every vertex has an even number of edges. Each time the pen passes a vertex, it uses one edge to arrive and one edge to leave.

What this node 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 node is. They do not measure its truth.

What this needs

To read this node, read these 9 nodes in this order. The foundations come first, and the list ends with this node.

Graph, definition, no evidence levelGraphdefinitionNeighbourhood, definition, no evidence levelNeighbourhooddefinitionWalk, definition, no evidence levelWalkdefinitionDegree of a vertex, definition, no evidence levelDegree of a vertexdefinitionReachability, definition, no evidence levelReachabilitydefinitionTrail, definition, no evidence levelTraildefinitionConnected graph, definition, no evidence levelConnected graphdefinitionEulerian trail, definition, no evidence levelEulerian traildefinitionEuler's theorem on Eulerian circuits, statement, no evidence levelEuler's theorem on Eu…statement
Each node uses the nodes above it. The colour of the bar on a box shows the evidence level, and the box also gives it as text. The list below has the same nodes.
  • no evidence level
  1. Graph definition
  2. Neighbourhood definition
  3. Walk definition
  4. Degree of a vertex definition
  5. Reachability definition
  6. Trail definition
  7. Connected graph definition
  8. Eulerian trail definition
  9. Euler's theorem on Eulerian circuits statement

Sources

  1. Web https://en.wikipedia.org/wiki/Eulerian_path, lead section

What links here

No node links to this node yet.