Vipul: Created page with "==Statement== Suppose $G$ is a finite undirected graph. The '''handshaking lemma''' says that the quantities (1)-(4) are all equal. Note that the equality of a..."

2014-05-25T19:19:32Z

Created page with "==Statement== Suppose <math>G</math> is a finite undirected graph. The '''handshaking lemma''' says that the quantities (1)-(4) are all equal. Note that the equality of a..."

New page

==Statement==

Suppose <math>G</math> is a [[finite undirected graph]]. The '''handshaking lemma''' says that the quantities (1)-(4) are all equal. Note that the equality of all the quantities apart from (1) is obvious, and the main content of the lemma is the equality with (1).

# Twice the number of edges of <math>G</math>.
# The sum of the [[degree of a vertex|degrees]] of all vertices of <math>G</math>.
# The sum of the elements of the [[degree sequence of a graph|degree sequence]] of <math>G</math>.
# The [[linear:trace of a matrix|trace]] of the [[degree matrix]] of <math>G</math>.

In particular, because the quantity defined by (1) is clearly an even nonnegative integer, it also shows that all the other quantities are even nonnegative integers.

Handshaking lemma - Revision history

Vipul: Created page with "==Statement== Suppose G is a finite undirected graph. The '''handshaking lemma''' says that the quantities (1)-(4) are all equal. Note that the equality of a..."

Vipul: Created page with "==Statement== Suppose $G$ is a finite undirected graph. The '''handshaking lemma''' says that the quantities (1)-(4) are all equal. Note that the equality of a..."