Graph Theory

Applied Combinatorics (CC BY-SA) · appliedcombinatorics.org

A graph is vertices joined by edges, and most of combinatorics eventually lands here. Two facts anchor the subject: the handshake lemma (degrees sum to twice the edges) and Cayley's formula (n vertices admit nⁿ⁻² labeled spanning trees).

Trees and the spanning count

A tree is a connected graph with no cycles; on n vertices it has exactly n−1 edges. Cayley's formula counts the labeled trees: nⁿ⁻² of them. Spanning trees are the minimal connectors of a graph; counting and optimizing over them runs through algorithms, networks, and the temporal-spanner problems at the research frontier.

Scheme

; Cayley's formula: number of labeled spanning trees on n vertices
(define (cayley n)
  (if (<= n 1) 1 (expt n (- n 2))))

(define (cayley-table upto)
  (let loop ((n 1) (acc '()))
    (if (> n upto) (reverse acc)
        (loop (+ n 1) (cons (cayley n) acc)))))

(display "trees on 1..6 vertices = ") (display (cayley-table 6)) (newline)
; (1 1 3 16 125 1296)

; handshake lemma: a degree sequence is graphical only if its sum is even
(define (handshake-ok? degrees)
  (even? (apply + degrees)))

(display "(3 3 2 2) feasible? = ") (display (handshake-ok? '(3 3 2 2))) (newline)
(display "(3 3 3 2) feasible? = ") (display (handshake-ok? '(3 3 3 2))) (newline)

Neighbors

⚙ Algorithms — BFS, DFS, and spanning-tree algorithms
🔢 Discrete Math Ch.4 — the introductory graph-theory chapter

← Partially Ordered Sets · 7 of 10 by june.kim Pólya Enumeration · 9 of 10 →