A graph is a set of vertices and a set of edges connecting pairs of them. That is the entire definition. From it you get trees, planarity, coloring, and the oldest theorem in graph theory: Euler's criterion for traversing every edge exactly once.
Graphs and degree
A graph G = (V, E) is a pair: a set of vertices and a set of edges. The degree of a vertex is the number of edges incident to it. The handshake lemma says the sum of all degrees equals 2|E|, because every edge contributes to two degrees.
Scheme
; Represent a graph as an adjacency list (list of pairs)
(define edges '((a b) (a c) (b c) (b d) (c d)))
; Degree of a vertex
(define (degree v edges)
(length (filter (lambda (e)
(or (equal? v (car e)) (equal? v (cadr e))))
edges)))
(display "deg(a) = ") (display (degree 'a edges)) (newline)
(display "deg(b) = ") (display (degree 'b edges)) (newline)
(display "deg(c) = ") (display (degree 'c edges)) (newline)
(display "deg(d) = ") (display (degree 'd edges)) (newline)
; Handshake lemma: sum of degrees = 2 * |E|
(define vertices '(a b c d))
(define sum-deg
(apply + (map (lambda (v) (degree v edges)) vertices)))
(display "Sum of degrees: ") (display sum-deg) (newline)
(display "2 * |E|: ") (display (* 2 (length edges)))
Python
edges = [('a','b'), ('a','c'), ('b','c'), ('b','d'), ('c','d')]
vertices = ['a', 'b', 'c', 'd']
degree = lambda v: sum(1for e in edges if v in e)
for v in vertices:
print(f"deg({v}) = {degree(v)}")
total = sum(degree(v) for v in vertices)
print(f"Sum of degrees: {total}, 2*|E|: {2*len(edges)}")
Paths, cycles, and connectivity
A path is a sequence of vertices where each consecutive pair is connected by an edge. A cycle is a path that starts and ends at the same vertex. A graph is connected if there is a path between every pair of vertices.
Scheme
; Adjacency list representation
(define graph '((a b c) (b a c d) (c a b d) (d b c)))
(define (neighbors v graph)
(let ((entry (assoc v graph)))
(if entry (cdr entry) '())))
; BFS to check connectivity
(define (bfs start graph)
(let loop ((queue (list start)) (visited '()))
(if (null? queue) visited
(let ((v (car queue)))
(if (member v visited)
(loop (cdr queue) visited)
(loop (append (cdr queue)
(filter (lambda (n) (not (member n visited)))
(neighbors v graph)))
(cons v visited)))))))
(define reachable (bfs 'a graph))
(display "Reachable from a: ") (display reachable) (newline)
(display "Connected? ")
(display (= (length reachable) (length graph)))
Python
fromcollectionsimport deque
graph = {'a': ['b','c'], 'b': ['a','c','d'], 'c': ['a','b','d'], 'd': ['b','c']}
def bfs(start):
visited, queue = set(), deque([start])
while queue:
v = queue.popleft()
if v notin visited:
visited.add(v)
queue.extend(n for n in graph[v] if n notin visited)
return visited
reachable = bfs('a')
print(f"Reachable from a: {reachable}")
print(f"Connected? {len(reachable) == len(graph)}")
Trees
A tree is a connected graph with no cycles. Equivalently, it is a connected graph on n vertices with exactly n-1 edges. Trees are minimal connected graphs: remove any edge and the graph disconnects.
Scheme
; A tree on 5 vertices has exactly 4 edges
(define tree-edges '((a b) (a c) (b d) (b e)))
(define tree-vertices '(a b c d e))
(display "Vertices: ") (display (length tree-vertices)) (newline)
(display "Edges: ") (display (length tree-edges)) (newline)
(display "Is |E| = |V|-1? ")
(display (= (length tree-edges) (- (length tree-vertices) 1))) (newline)
; Every tree is a spanning tree of itself.; The number of labeled trees on n vertices is n^(n-2) (Cayley's formula).
(display "Labeled trees on 4 vertices: ")
(display (expt 42)) (newline) ; 16
(display "Labeled trees on 5 vertices: ")
(display (expt 53)) ; 125
An Euler path traverses every edge exactly once. Euler proved it exists if and only if exactly 0 or 2 vertices have odd degree. A Hamilton path visits every vertex exactly once. No efficient test is known for Hamilton paths; this is one of the NP-complete problems.
Scheme
; Check for Euler path/circuit
(define (degree v edges)
(length (filter (lambda (e)
(or (equal? v (car e)) (equal? v (cadr e))))
edges)))
; Konigsberg bridges
(define konigsberg '((A C) (A C) (A D) (B C) (B C) (B D) (C D)))
(define k-verts '(A B C D))
(define odd-degrees
(filter (lambda (v) (odd? (degree v konigsberg))) k-verts))
(display "Konigsberg odd-degree vertices: ")
(display odd-degrees) (newline)
(display "Count: ") (display (length odd-degrees)) (newline)
(display "Euler path exists? ")
(display (or (= (length odd-degrees) 0)
(= (length odd-degrees) 2))) (newline)
; A graph with Euler circuit: all even degrees
(define square '((a b) (b c) (c d) (d a)))
(define sq-verts '(a b c d))
(define sq-odd
(filter (lambda (v) (odd? (degree v square))) sq-verts))
(display "Square graph odd-degree: ")
(display (length sq-odd)) (newline)
(display "Euler circuit exists? ")
(display (= (length sq-odd) 0))
Python
konigsberg = [('A','C'),('A','C'),('A','D'),('B','C'),('B','C'),('B','D'),('C','D')]
verts = ['A','B','C','D']
deg = lambda v: sum(1for e in konigsberg if v in e)
odd = [v for v in verts if deg(v) % 2 == 1]
print(f"Odd-degree vertices: {odd} (count: {len(odd)})")
print(f"Euler path? {len(odd) in (0, 2)}")
Planar graphs and coloring
A graph is planar if it can be drawn without edge crossings. Euler's formula for connected planar graphs: V - E + F = 2, where F is the number of faces. The four color theorem says every planar graph can be vertex-colored with at most 4 colors so that no two adjacent vertices share a color.
Scheme
; Euler's formula: V - E + F = 2; For a planar graph, check the formula; Tetrahedron (K4): V=4, E=6, F=4
(display "K4: V-E+F = ")
(display (+ (- 46) 4)) (newline) ; 2; Cube: V=8, E=12, F=6
(display "Cube: V-E+F = ")
(display (+ (- 812) 6)) (newline) ; 2; Corollary: for simple planar graph, E <= 3V - 6; K5 has V=5, E=10. Is 10 <= 3*5-6 = 9? No. So K5 is not planar.
(display "K5: E=10, 3V-6=") (display (- (* 35) 6)) (newline)
(display "K5 planar? ") (display (<= 109)) (newline)
; Greedy coloring (not optimal, but illustrative)
(define graph '((a b c) (b a c d) (c a b d) (d b c)))
(define (greedy-color graph)
(let loop ((vs (map car graph)) (coloring '()))
(if (null? vs) coloring
(let* ((v (car vs))
(nbrs (cdr (assoc v graph)))
(used (filter-map
(lambda (n) (let ((c (assoc n coloring)))
(if c (cdr c) #f)))
nbrs))
(color (let find ((c 1))
(if (not (member c used)) c (find (+ c 1))))))
(loop (cdr vs) (cons (cons v color) coloring))))))
(display "Greedy coloring: ")
(display (greedy-color graph))
Python
# Euler's formulafor name, v, e, f in [("K4",4,6,4), ("Cube",8,12,6)]:
print(f"{name}: V-E+F = {v - e + f}")
# K5 planarity checkprint(f"K5: E=10, 3V-6={3*5-6}, planar? {10 <= 3*5-6}")
# Greedy coloring
graph = {'a':['b','c'], 'b':['a','c','d'], 'c':['a','b','d'], 'd':['b','c']}
coloring = {}
for v in graph:
used = {coloring[n] for n in graph[v] if n in coloring}
coloring[v] = next(c for c inrange(1, 100) if c notin used)
print(f"Greedy coloring: {coloring}")
Notation reference
Math
Scheme
Python
Meaning
G = (V, E)
adj list
dict
Graph
deg(v)
(degree v edges)
degree(v)
Vertex degree
V - E + F = 2
(+ (- v e) f)
v - e + f
Euler's formula (planar)
K_n
complete graph
complete graph
Complete graph on n vertices
chi(G)
greedy-color
greedy color
Chromatic number
Neighbors
Other chapter pages
Grinstead Ch.11 โ Markov chains: random walks on directed graphs
Graphs are represented as adjacency lists in both Scheme and Python. The greedy coloring algorithm is not guaranteed to find the optimal coloring (the chromatic number is NP-hard to compute). Euler's criterion for Euler paths is a theorem, not a heuristic: the "if and only if" is exact. Hamilton paths have no such clean characterization, which is why the problem is NP-complete.
Seven Bridges of Konigsberg