Day 59 — Graphs & handshaking

Updated

July 30, 2026

Day 59 — Graphs & handshaking

Stage VI · concept day
Goal: Define simple, multi, and directed graphs; prove the handshaking lemma; apply Havel–Hakimi to graphic sequences; recognize \(K_n\), \(C_n\), \(P_n\), \(K_{m,n}\); awareness of isomorphism.

Why this matters

Graphs model networks, dependencies, social links, call graphs, and state transitions. Degree and the handshaking lemma are the first global constraints: you cannot invent arbitrary degree lists. Everything in Stage VI builds on today’s vocabulary.

Theory

Undirected graph

An undirected graph \(G=(V,E)\) consists of a finite vertex set \(V\) and an edge set \(E\).

Simple graph: elements of \(E\) are 2-element subsets of \(V\) (no loops, no parallel edges).
Order \(n=|V|\), size \(m=|E|\).
Vertices \(u,v\) are adjacent if \(\{u,v\}\in E\); edge incident to its endpoints.
Neighbor set \(N(v)\); degree \(\deg(v)=|N(v)|\) in a simple graph.

Multigraphs allow parallel edges between the same pair; loops are edges with both ends the same vertex (a loop contributes \(2\) to degree). Unless stated, assume simple undirected graphs.

Directed graphs (digraphs)

\(G=(V,E)\) with \(E\subseteq V\times V\) (ordered pairs).
Out-degree \(\mathrm{deg}^+(v)\), in-degree \(\mathrm{deg}^-(v)\).
Loops and bidirected pairs possible depending on model.

Drawings vs abstract graphs

A picture is a representation. The abstract graph is \(V\) and \(E\) only. Two drawings may depict the same graph.

Handshaking lemma

Theorem (undirected). For any finite undirected graph (simple or multi),

\[ \sum_{v\in V}\deg(v) = 2|E|. \]

Proof. Each edge contributes exactly \(2\) to the degree sum (one for each endpoint; a loop contributes 2 to one vertex). Summing degrees counts every edge twice. \(\square\)

Corollary. The number of odd-degree vertices is even.

Proof. \(\sum\deg\) even ⇒ even number of odd summands. \(\square\)

Directed handshaking:

\[ \sum_v \mathrm{deg}^+(v) = \sum_v \mathrm{deg}^-(v) = |E|. \]

Each arc contributes 1 to one out-degree and 1 to one in-degree.

Graphic sequences

A sequence \(d_1\ge d_2\ge\cdots\ge d_n\ge 0\) of integers is graphic if some simple graph on \(n\) vertices has those degrees.

Necessary conditions: \(\sum d_i\) even; each \(d_i\le n-1\).

Havel–Hakimi algorithm

Theorem (Havel–Hakimi). Let \(d_1\ge\cdots\ge d_n\). The sequence is graphic iff the sequence obtained by deleting \(d_1\) and subtracting 1 from the next \(d_1\) terms, then resorting, is graphic (on \(n-1\) vertices). Empty/all-zero is graphic.

Worked use: iterate until zeros (success) or a negative entry / impossibility (fail).

Special graphs

Symbol	Name	Edges / notes
\(K_n\)	Complete	\(\binom{n}{2}\) edges; \(\deg=n-1\)
\(P_n\)	Path on \(n\) vertices	\(n-1\) edges; ends deg 1
\(C_n\)	Cycle \(n\ge 3\)	\(n\) edges; 2-regular
\(K_{m,n}\)	Complete bipartite	\(mn\) edges; parts \(m,n\)
\(\overline{G}\)	Complement	edges of \(K_n\) not in \(G\)
Empty \(E_n\)	No edges	all deg 0

Regular: all degrees equal \(k\) (\(k\)-regular). \(K_n\) is \((n-1)\)-regular; \(C_n\) is 2-regular.

Isomorphism (awareness)

\(G\cong H\) if there is a bijection \(f:V(G)\to V(H)\) with \(\{u,v\}\in E(G)\iff\{f(u),f(v)\}\in E(H)\).
Same degree sequence is necessary not sufficient. Testing isomorphism is subtle (not needed algorithmically here).

Subgraphs

\(H\) is a subgraph of \(G\) if \(V(H)\subseteq V(G)\) and \(E(H)\subseteq E(G)\).
Induced subgraph: all edges of \(G\) among a vertex subset.

Worked examples

Example 1 — Handshaking

Degrees \(3,3,2,2,2,2\): sum \(14=2|E|\) ⇒ \(|E|=7\). Four odd? Only two odds—OK.

Example 2 — Impossible

Degrees \(3,3,3\): sum 9 odd—impossible.

Example 3 — \(K_5\)

\(|E|=\binom{5}{2}=10\); each deg 4.

Example 4 — \(K_{2,3}\)

Edges \(6\); degrees \(3,3\) on the part of size 2; \(2,2,2\) on the part of size 3.

Example 5 — Havel–Hakimi

Sequence \((3,3,3,1,1,1)\): sort already. Remove 3, subtract from next 3: \((2,2,0,1,1)\) → sort \((2,2,1,1,0)\).
Remove 2: \((1,0,1,0)\) → sort \((1,1,0,0)\).
Remove 1: \((0,0,0)\). Success—graphic.

Example 6 — Havel fail

\((3,3,3,1)\): remove 3 → \((2,2,0)\) sort \((2,2,0)\); remove 2 → \((1,-1)\) negative—not graphic.

Example 7 — Complement degrees

If \(\deg_G(v)=d\), then \(\deg_{\overline{G}}(v)=n-1-d\).

Example 8 — Directed

Arcs \(a\to b, b\to c, a\to c, c\to a\): out-degrees \((2,1,1)\), in \((1,1,2)\); sums = 4.

Example 9 — Max edges simple

On \(n\) verts: \(\binom{n}{2}\). Min for connected: \(n-1\) (trees, Day 61).

Example 10 — Same degree theorem

Any simple \(G\) on \(n\ge 2\) has two vertices of equal degree (Day 45 PHP + no both 0 and \(n-1\)).

Example 11 — \(C_4\) vs \(K_{2,2}\)

\(C_4\cong K_{2,2}\)—same abstract graph.

Example 12 — Multigraph handshaking

Two vertices, three parallel edges: degrees 3,3; sum 6 = \(2\cdot 3\).

Example 13 — Regular existence

Is 3-regular on 5 vertices possible? Sum \(15\) odd—impossible.

Example 14 — \(k\)-regular on \(n\) verts

Need \(kn\) even; \(k\le n-1\). Not always sufficient (e.g. 3-regular on 6 verts exists: utility graph \(K_{3,3}\)).

Example 15 — Count labeled graphs

Number of simple labeled graphs on \(n\) verts: \(2^{\binom{n}{2}}\) (each possible edge in or out).

Exercises

Define simple undirected graph carefully.
Degrees \(4,3,3,2,2,2\): \(|E|\)? Number of odd-degree vertices?
Prove handshaking lemma in your own words.
Prove number of odd-degree vertices is even.
\(|E(K_7)|\) and degree of each vertex.
Draw \(P_5\), \(C_5\), \(K_{1,4}\) (star).
Is \((5,4,3,2,1,1)\) graphic? Run Havel–Hakimi.
Is \((6,5,4,3,2,1,0)\) graphic on 7 verts?
Directed: construct arcs realizing out-degrees \((2,1,0)\) and in-degrees \((1,1,1)\) if possible.
Prove \(\sum\deg^+=\sum\deg^-=|E|\).
Edges in \(k\)-regular graph on \(n\) verts.
Complement of \(C_5\): degrees?
Show \(K_n\) is the unique simple graph with all degrees \(n-1\).
Can a simple graph have degrees \(1,1,1,1\)? Draw or disprove connectivity later—existence: yes \(2K_2\).
Count labeled simple graphs with exactly 1 edge on \(n\) verts.
CS: undirected coauthorship vs directed citation—interpret degree.
Why is \((2,2,2,2)\) graphic two nonisomorphic ways on 4 verts? (\(C_4\) only up to iso for simple connected—actually only \(C_4\). On multigraphs different.)
Havel–Hakimi on \((4,3,3,3,3)\).
Max size of simple bipartite graph on parts \(3+3\).
True/false: same degree sequence ⇒ isomorphic.
Loop contribution to degree: why 2?
Find all nonisomorphic simple graphs on 3 vertices.
If \(\sum\deg=2n-2\) and connected, tree? (preview Day 61: yes.)
Challenge: Erdős–Gállai statement awareness (optional).
Number of simple graphs on 4 labeled verts: \(2^6=64\).

CS connection

Social / trust graphs: undirected friendship; directed follow.
Dependency graphs: directed packages.
Networks: degree distribution as first statistic.
Matrix: adjacency matrix \(A\); \(\deg(v)\) = row sum undirected.
Resource equality: handshaking as invariant in rewiring.

Common pitfalls

Pitfall	What to do instead
Sum of degrees odd accepted	Must be even
\(d_i\ge n\) in simple graph	Max \(n-1\)
Multigraph vs simple confusion	State model
Drawing equality as isomorphism	Check abstract \(E\)
Directed degrees mixed	Separate in/out

Checkpoint

Two personal takeaways:

Selected mini-solutions

Sum 16 ⇒ 8 edges; two odds (the two 3s).
\(21\); deg 6.
Try HH… may fail or succeed—work carefully.
Max deg 6 OK; HH: often fails because of 0 with 6 (isolated vs universal)—not graphic.
\(|E|=kn/2\).
\(\binom{\binom{n}{2}}{1}=\binom{n}{2}\).
\((4,3,3,3,3)\) → delete 4 → \((2,2,2,2)\) → \((1,1,2,2)\) sort \((2,2,1,1)\) → \((1,0,1)\) sort \((1,1,0)\) → \((0,0)\) OK.

Deepening notes

Handshaking proof (rewrite)

Each edge \(\{u,v\}\) is counted in \(\deg(u)\) and in \(\deg(v)\). Summing degrees therefore equals \(2|E|\). For loops in multigraphs, the loop is incident twice to its vertex by convention—still +2.

Havel–Hakimi worked checklist

Sort nonincreasing.
If \(d_1>n-1\) or negative appears later → fail.
Delete \(d_1\), subtract 1 from next \(d_1\) entries.
Resort; repeat.
All zeros → graphic.

Degree sequence vs isomorphism

Same degree sequence does not imply isomorphic: e.g. two nonisomorphic graphs on 6 vertices both 2-regular (disjoint cycles \(C_3\cup C_3\) vs \(C_6\)).

Extra drills

D1. Graphic? \((4,4,3,3,2,2)\).
D2. Graphic? \((5,3,3,3,3,3)\).
D3. Edges in 4-regular on 10 verts.
D4. Draw all simple graphs on 4 labeled verts with 2 edges.
D5. Directed handshaking numeric invent.
D6. Complement degrees of \((3,2,2,1)\) on 4 verts.
D7. Prove no 3-regular graph on 5 verts.
D8. \(|E(K_{m,n})|=mn\) proof by product.

Flash

\(\sum\deg=2|E|\); odd degrees even count; labeled graphs \(2^{\binom{n}{2}}\).

Exam drill block

E1. State definitions: simple graph, multigraph, digraph, degree, regular.
E2. Handshaking full proof (undirected + directed).
E3. HH on \((4,3,3,2,2,2)\) step-by-step.
E4. Is \((3,3,3,3,3)\) graphic? Why not?
E5. Edges and degrees in \(K_6\), \(C_6\), \(K_{3,4}\), \(P_6\).
E6. Number of simple labeled graphs on 5 verts; number with exactly 3 edges.
E7. If \(G\) is \(k\)-regular on \(n\) verts, when is \(\overline{G}\) regular and of what degree?
E8. Construct a digraph with out-degrees \((2,2,1,1)\) and equal in-sum.
E9. Prove: in any group of 6 people at a party modeled by a graph, two have same number of handshakes (PHP + degrees).
E10. True/false battery: (i) every sequence of even sum is graphic (ii) \(K_n\) is \((n-1)\)-regular (iii) multigraphs can have odd degree sum.

Mini solutions

E3. Should succeed after few HH steps (verify).
E4. Sum 15 odd—impossible.
E5. \(15\); \(6\); \(12\); \(5\).
E6. \(2^{10}=1024\); \(\binom{10}{3}=120\).
E7. Degree \(n-1-k\) each; always regular.
E10. F; T; F (sum always even).

Special graphs quick sheet

Graph	\(\|V\|\)	\(\|E\|\)	Degrees
\(K_n\)	\(n\)	\(\binom{n}{2}\)	\(n-1\) each
\(P_n\)	\(n\)	\(n-1\)	two \(1\)s, rest \(2\)
\(C_n\)	\(n\)	\(n\)	\(2\) each
\(K_{m,n}\)	\(m+n\)	\(mn\)	\(n\) on left, \(m\) on right
\(Q_d\) hypercube	\(2^d\)	\(d\cdot 2^{d-1}\)	\(d\) each

Directed handshaking

\(\sum_v \mathrm{indeg}(v)=\sum_v \mathrm{outdeg}(v)=|A|\) (arc set). Every arc contributes one to one out-degree and one to one in-degree.

Synthesis

Graphs are \(G=(V,E)\) with optional directions and multiplicities. Handshaking \(\sum\deg=2|E|\) forces an even number of odd-degree vertices—the first global invariant. Graphic sequences: Havel–Hakimi or Erdős–Gállai; same degree sequence ≠ isomorphism. Complements, regular graphs, and bipartite complete graphs are the standard zoo.

S1. Full HH on \((5,4,3,3,2,2,1)\)—graphic or not.
S2. Prove no \(3\)-regular graph on \(9\) vertices.
S3. Cold: edges in \(K_7\), \(K_{3,5}\), \(Q_4\); number of odds in any graph.

Modeling hint for later days

Vertices = entities; edges = symmetric relations. Degrees = load/popularity. Tomorrow: moving around the graph (walks, paths, connectivity).

Complement and regularity

If \(G\) is simple on \(n\) vertices with degree sequence \((d_1,\ldots,d_n)\), then \(\overline{G}\) has degrees \((n-1-d_1,\ldots,n-1-d_n)\).
If \(G\) is \(k\)-regular, then \(\overline{G}\) is \((n-1-k)\)-regular.
\(|E(\overline{G})|=\binom{n}{2}-|E(G)|\).

Worked HH recap

Sequence \((3,3,2,2,2)\): sort OK; delete first 3 → subtract from next three → \((2,1,1,2)\) sort \((2,2,1,1)\); delete 2 → \((1,0,1)\) sort \((1,1,0)\); delete 1 → \((0,0)\). Graphic.

More cold drills

C1. Edges in a 4-regular graph on 12 verts.
C2. Why \((2,2,2,2,2)\) is graphic (\(C_5\)) but so is \(C_3\cup C_2\) only if multigraph—simple: \(C_5\) only up to iso on 5 verts 2-regular.
C3. Directed: construct in/out degrees both \((2,1,1,0)\) summing equal.

C1. \(|E|=4\cdot 12/2=24\).

Tomorrow

Day 60 — Paths, cycles, connectivity: walk/trail/path/cycle; components; cut vertices/edges lite; distance; digraph strong connectivity.