Why the number of people who have shaken hands an odd number of times is even
In short: In graph theory, the degree of a vertex is simply the number of edges connected to it. This seemingly simple count reveals deep structural truths about networks, including the handshaking lemma, which proves that in any group, the number of people who have shaken an odd number of hands is always even.
The degree of a vertex acts as a fundamental descriptor of a graph's architecture. For an undirected graph, the degree sum formula establishes that the sum of all vertex degrees is exactly twice the number of edges. This relationship leads directly to the handshaking lemma, which dictates that any undirected graph must contain an even number of vertices with an odd degree. This is not just a theoretical curiosity; it provides a rigorous basis for understanding network connectivity, such as determining whether an Eulerian path—a path that visits every edge exactly once—can exist within a specific structure.
Beyond simple counts, the degree sequence—the list of vertex degrees arranged in non-increasing order—serves as a graph invariant. While isomorphic graphs share the same degree sequence, this sequence does not always uniquely identify a graph. Graphs that are uniquely determined by their degree sequence are known as unigraphs. The challenge of determining whether a given sequence of integers can represent a simple graph is known as the graph realization problem, which can be addressed using the Havel-Hakimi algorithm or the Erdős-Gallai theorem.
Degrees also define specific graph classes and properties. A regular graph, for instance, features vertices that all share the same degree, while a complete graph represents the extreme case where every vertex reaches the maximum possible degree. In more complex scenarios, such as signed graphs, researchers distinguish between positive and negative degrees. These metrics are vital for advanced graph theory applications, including Brooks' theorem, which relates the maximum degree of a graph to its chromatic number, and the study of degenerate graphs, where every subgraph contains a vertex of limited degree.
Opens the Intellect+ feed with this card first. Swipe up for the next one.
Sources
- Summary by Intellect · source: Degree (graph theory)
To cite this card, link to https://intellectplus.co.uk/app/science-degree-graph-theory.
How we source, check and correct cards: Editorial standards.
General information, not professional advice. Spotted an error? Flag the card or see corrections and complaints.
Intellect Plus is a visual educational discovery platform for exploring fascinating facts and ideas. Brain Food, Not Brain Rot. What is Intellect Plus?
Related
More in Discrete mathematics · More in Science · Latest · A–Z · All topics