Math 2.0

Combinatorics Graph theory: basic notions Theorem

Handshaking lemma

Builds on Edge setDegree of a vertex

Statement

Let GG be a finite graph with vertex set VV and edge set EE. Then ∑v∈Vdeg⁡(v)=2 ∣E∣.\sum_{v \in V} \deg(v) = 2\, |E|.

Remarks

Proof: count the pairs (v,e)(v, e) with v∈ev \in e. Each edge has two ends, and each vertex vv lies in deg⁡(v)\deg(v) edges. This is double counting. A direct consequence is that the number of odd-degree vertices is even. For a 33-regular graph on nn vertices, it gives 3n=2∣E∣3n = 2 |E|, so nn is even.

Reading path

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

Show the path as a graph
Graph, definition, no evidence levelGraphdefinitionEdge set, definition, no evidence levelEdge setdefinitionNeighbourhood, definition, no evidence levelNeighbourhooddefinitionDegree of a vertex, definition, no evidence levelDegree of a vertexdefinitionHandshaking lemma, statement, no evidence levelHandshaking lemmastatement
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. Edge set definition
  3. Neighbourhood definition
  4. Degree of a vertex definition
  5. Handshaking lemma statement

Where this leads

1 page builds on this one.

Further reading

  1. Web https://en.wikipedia.org/wiki/Handshaking_lemma, Definitions and statement
About this page
Tag0XAP8WHNES
URIm2://0XAP8WHNES
Kindstatement, theorem
WritingW0 stub
MSC05C07
StatusThis copy of the site has no build data. Run m2 status 0XAP8WHNES.
UsesEdge set, Degree of a vertex
Same as

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

Used by