xv. Graph Constructions

Target	Construction
simple graph with degree sequence $d$	Havel–Hakimi: connect the max-degree vertex to the next $d$ largest, repeat
bipartite graph with degree sequences	Gale–Ryser condition; greedy fill largest first
tree with $n$ vertices and diameter $d$	a path of length $d$, hang the rest on an inner vertex
tree with given degrees ($\sum d=2n-2$, all $\ge 1$)	Prüfer-style: repeatedly join a leaf to the smallest vertex that still needs edges
graph with exactly $k$ shortest paths from $s$ to $t$	binary layers: a ladder of “diamonds” doubling the count, with shortcuts for the set bits of $k$
triangle-free graph with chromatic number $k$	Mycielski construction
max edges without $K_{r+1}$	Turán graph: $r$ near-equal parts, all edges between parts
strongly connected orientation	DFS tree edges downward, back edges upward (needs 2-edge-connected)
regular graph of degree $k$ on $n$ vertices	circulant: connect $i$ to $i\pm 1,\dots ,i\pm k/2$ (plus $i+n/2$ if $k$ odd, $n$ even)

Havel–Hakimi

vector<pair<int, int>> havelHakimi(vector<int> d) {   // simple graph with degrees d, or {{-1,-1}} if not graphical
    int n = sz(d); vector<pair<int, int>> e;
    vector<int> id(n); iota(all(id), 0);
    while (true) {
        sort(all(id), [&](int x, int y) { return d[x] > d[y]; });
        int v = id[0]; if (d[v] == 0) break;
        if (d[v] > n - 1) return {{-1, -1}};
        for (int i = 1; i <= d[v]; i++) {
            int u = id[i]; if (d[u] == 0) return {{-1, -1}};
            d[u]--; e.push_back({v, u});
        }
        d[v] = 0;
    }
    return e;
}

Proof: Havel–Hakimi is correct

Let $v$ have maximum degree $d_v$. Claim: if $d$ is graphical, there is a realization in which $v$ is adjacent to the $d_v$ vertices of largest remaining degree. Take any realization; if $v$ is adjacent to $x$ but not to $y$ with $d_y>d_x$ (or equal and $y$ preferred), then $y$ has a neighbour $z\ne v$ not adjacent to $x$ (since $y$ has more neighbours outside $v$ than $x$ does). Replace edges $vx,yz$ by $vy,xz$: degrees are unchanged, and $v$‘s neighbourhood improved. Repeating gives the claim. Removing $v$ and decrementing its neighbours leaves a graphical sequence iff the original was graphical, so the greedy succeeds exactly on graphical sequences. Verified against all graphs on $\le 5$ vertices.

Tree with a given diameter

vector<pair<int, int>> treeWithDiameter(int n, int d) {  // vertices 0..n-1; exists iff 1 <= d <= n-1 and (d >= 2 or n == 2)
    if (d < 1 || d > n - 1 || (d == 1 && n > 2)) return {};
    vector<pair<int, int>> e;
    for (int i = 0; i < d; i++) e.push_back({i, i + 1});    // the diameter path 0..d
    for (int v = d + 1; v < n; v++) e.push_back({1, v});     // hang the rest on vertex 1 (not an end)
    return e;
}

Proof: the diameter stays d

The path $\mathrm{0..}d$ has length $d$. A hung vertex $v$ is at distance $1$ from vertex $1$, so its distance to any path vertex $i$ is $1+|i-1|\le d$ (since $d\ge 2$), and two hung vertices are at distance $2\le d$. A tree on $n\ge 3$ vertices has a vertex of degree $\ge 2$, so its diameter is at least $2$, which is why $d=1$ only works for $n=2$. Verified by BFS for all $n\le 30$.

Related: Special Graphs, Prüfer Codes.