if you add up the degrees of all the vertices of a finite graph then the result will be twice the number of edges, provided that the vertices are odd-degree. What is the name of this theorem? why does it require that the graph be undirected?
[Math] The number of odd-degree vertices is even in a finite graph
graph theory
Best Answer
It is known as the handshaking lemma because if a bunch of people shake hands and you add up the number of hands each person shook, you get an even number. Each handshake adds two to the total. It does not require that each vertex be of odd degree, but it shows there are an even number of vertices of odd degree. For a directed graph, this is still true if you add all the indegrees and outdegrees for the same reason, but the sum of indegrees need not be even. Think of a directed graph with two vertices and one directed edge connecting them.