Degree sequences and the Handshaking Lemma are key concepts in graph theory. They help us understand graph structure and connectivity without needing to know exact edge arrangements. These tools are super useful for analyzing networks in various fields.

The Handshaking Lemma connects vertex degrees to edge count, leading to cool insights. It's a fundamental principle that shows up in many graph theory problems and real-world applications. Understanding these ideas is crucial for tackling more complex graph concepts.

Degree sequences of graphs

Definition and properties

• Degree sequence represents an ordered list of vertex degrees in a graph, typically arranged in non-increasing order
• Vertex degree in undirected graphs measures the number of edges connected to that vertex
• Directed graphs include both in-degrees and out-degrees for each vertex in the sequence
• Provides crucial information about graph structure and connectivity without specifying exact edge arrangement
• Sum of all degrees in a sequence always equals an even number for undirected graphs (each edge contributes two to the total)
• Utilized to classify and compare different graphs, even non-isomorphic ones
• Characteristic sequences exist for special graph types (regular graphs have identical entries for all vertices)

Applications and examples

• Helps analyze network structures in social networks (Facebook friend counts)
• Aids in studying biological networks (protein interaction degrees in cells)
• Useful for computer network design (router connection degrees)
• Examples of degree sequences:
  • Complete graph on 4 vertices: [3, 3, 3, 3]
  • Path graph on 5 vertices: [2, 2, 2, 1, 1]
  • Star graph with 6 vertices: [5, 1, 1, 1, 1, 1]
• Degree sequence analysis reveals graph properties:
  • Maximum degree indicates the most connected vertex
  • Minimum degree shows the least connected vertex
  • Average degree provides overall connectivity measure

Handshaking Lemma

Statement and proof

• Handshaking Lemma states the sum of all vertex degrees equals twice the number of edges in any undirected graph
• Mathematically expressed as $\sum_{v \in V} \deg(v) = 2|E|$, where V represents vertex set and E represents edge set
• Proof relies on each edge contributing exactly two to the degree sum (one for each endpoint)
• Proved through induction on edge count or simple counting argument
• Counting argument proof:
  1. Each edge connects two vertices
  2. Counting degrees sums the edge contributions
  3. Total contribution equals twice the edge count
• Applies to multigraphs and pseudographs (self-loops contribute two to incident vertex degree)

Implications and applications

• Corollary states the number of odd-degree vertices in any graph must be even
• Useful for solving various graph theory problems:
  • Determining if a graph has an Eulerian circuit (all vertices have even degree)
  • Analyzing network traffic flow (sum of in-degrees equals sum of out-degrees)
• Applications in real-world scenarios:
  • Social network analysis (total friendships equal twice the connection count)
  • Transportation networks (total road endpoints equal twice the road count)
• Examples:
  • Graph with degree sequence [3, 3, 2, 2, 2] has 6 edges: (3 + 3 + 2 + 2 + 2) / 2 = 6
  • Complete graph $K_n$ has $\frac{n(n-1)}{2}$ edges: $\frac{n(n-1)}{2} = \frac{\sum_{i=1}^n (n-1)}{2}$

Valid degree sequences

Erdős-Gallai theorem and conditions

• Erdős-Gallai theorem provides necessary and sufficient conditions for a sequence to be realizable as a simple graph
• Theorem statement: A sequence $d_1 \geq d_2 \geq ... \geq d_n$ is graphical if and only if sum of $d_i$ is even and $\sum_{i=1}^k d_i \leq k(k-1) + \sum_{i=k+1}^n \min(d_i, k)$ for all $k = 1, 2, ..., n$
• Necessary (but not sufficient) condition requires even sum of all sequence entries
• Directed graphs require in-degree and out-degree sequences to have equal sums and satisfy specific conditions
• Bipartite degree sequences use majorization concept and Gale-Ryser theorem for realizability

Algorithms and verification methods

• Havel-Hakimi algorithm determines if a sequence is graphical through iterative reductions
• Algorithm steps:
  1. Sort sequence in descending order
  2. Remove largest element $d_1$
  3. Subtract 1 from the next $d_1$ elements
  4. Repeat until all elements are 0 (graphical) or a negative number appears (not graphical)
• Example: Is [4, 3, 3, 2, 2] graphical?
  • [3, 2, 2, 1] → [1, 1, 1] → [0, 0] (graphical)
• Efficient for quick verification of potential degree sequences
• Understanding these methods crucial for analyzing and constructing graphs with specific degree distributions

Graph construction with degree sequences

Construction techniques

• Havel-Hakimi algorithm serves as constructive method to build graphs with given degree sequences
• Multiple non-isomorphic graphs may realize the same graphical sequence
• Iterative vertex connection process maintains desired degrees during construction
• Simple graph construction requires avoiding self-loops and multiple edges
• Directed graph construction balances in-degrees and out-degrees simultaneously
• Bipartite graph construction matches vertices from two partite sets while satisfying degree constraints

Applications and examples

• Random graph generation with specific degree distributions:
  • Network science applications (scale-free networks)
  • Complex system modeling (social network simulations)
• Example construction process for [3, 3, 2, 2, 2]:
  1. Connect highest degree vertex to next three highest
  2. Connect remaining edges to satisfy degrees
  3. Result: pentagon with two crossing edges
• Importance in analyzing real-world networks:
  • Internet topology studies
  • Ecological food web modeling
• Graph reconstruction problems:
  • Determine if multiple graphs share the same degree sequence
  • Applications in chemistry (molecular structure analysis)