statement theorem
Degrees along an Eulerian trail
Statement
Let be a finite graph, and let be an Eulerian trail of from to . If , then every vertex of has even degree. If , then and have odd degree and every other vertex has even degree.
Remarks
Proof idea: each time 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 or vertices of odd degree. The Seven Bridges of Königsberg have .
Explanations
L1 human
Count the edges at a vertex as a walk uses them. Every visit in the middle of the walk uses one edge in and one edge out. Only the first and last vertices can be left with an odd count.
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 7 nodes in this order. The foundations come first, and the list ends with this node.
- no evidence level
- Graph definition
- Neighbourhood definition
- Walk definition
- Degree of a vertex definition
- Trail definition
- Eulerian trail definition
- Degrees along an Eulerian trail statement
Sources
- Web https://en.wikipedia.org/wiki/Eulerian_path, Properties
What links here
No node links to this node yet.