Capstone B: Extremal Graph Discovery

A forbidden-subgraph question with a known baseline

The project asks: how many edges can a finite simple undirected graph have without containing a four-cycle? Fix the forbidden graph $C_4$ with distinct vertices $0,1,2,3$ and edges $01,12,23,30$. Containment means an injective map preserving these edges, not an induced copy. Extra edges among the selected vertices are allowed. In particular, $K_4$ contains a forbidden four-cycle even though its four vertices do not induce a chordless cycle.

Let $\operatorname{ex}(n,C_4)$ be the maximum edge count among such avoiding graphs on $n$ vertices. We enumerate all labeled instances for $0\le n\le5$, organize them into unlabeled isomorphism classes, and compare the maxima with a classical benchmark. A graph isomorphism is a bijection of vertices preserving adjacency; an unlabeled graph here means one isomorphism class, not a graph with its isolated vertices removed.

The benchmark is Reiman's upper bound, proved below:

$$\operatorname{ex}(n,C_4)\le\left\lfloor\frac n4\left(1+\sqrt{4n-3}\right)\right\rfloor\qquad(n\ge1).$$

Set $\operatorname{ex}(0,C_4)=0$ separately. The bound gives an independently derived ceiling against which to check a search; it does not claim an exact formula at every order. Review extremal graph theory, combinatorial algorithms, and experimental and computational combinatorics for the supporting methods. All assumptions needed for the worked project are stated here.

Enumerating graphs without hiding symmetry

Order unordered vertex pairs lexicographically. Bit $i$ of an integer mask specifies whether the $i$th pair is an edge. Every $n$-vertex labeled graph then occurs once among $2^{\binom n2}$ masks. The vertex count is stored separately, so masks representing empty graphs of different orders are different records.

For these small orders, define the canonical representative to be the smallest mask obtained over all vertex permutations. Equal canonical masks, at the same vertex count, are equivalent exactly when the graphs are isomorphic: relabeling preserves the orbit, and a common representative supplies an isomorphism. A degree sequence alone is not canonical; nonisomorphic graphs can have identical degrees.

The program below independently tests adjacency-preserving bijections using a separate matrix comparison. It verifies that every input is isomorphic to its representative, that distinct representatives are not isomorphic, and that each bucket equals the full relabeling orbit. It also checks the orbit–stabilizer identity $\lvert\operatorname{Orb}(G)\rvert\lvert\operatorname{Aut}(G)\rvert=n!$, counting automorphisms directly. These checks establish both coverage and separation of the computed classes rather than merely trusting a hash.

Save the panel as extremal_lab.py, then run python3 extremal_lab.py in an empty output directory. The reference interpreter was Python 3.12.14. It writes extremal-data.json, containing generation parameters, every labeled record, canonical representatives, certificates, summaries, and the eight-vertex counterexample. All arithmetic deciding feasibility and the benchmark ceiling is exact. This deliberately small program uses no third-party graph package.

from collections import defaultdict
from itertools import combinations, permutations
from math import factorial, isqrt
from pathlib import Path
import hashlib
import json
import sys


def matrix(n, mask):
    a = [[0] * n for _ in range(n)]
    for bit, (u, v) in enumerate(combinations(range(n), 2)):
        a[u][v] = a[v][u] = (mask >> bit) & 1
    return a


def encode(a, order):
    return sum(a[order[u]][order[v]] << bit
               for bit, (u, v) in enumerate(combinations(range(len(a)), 2)))


def canonical(a):
    return min(encode(a, p) for p in permutations(range(len(a))))


def c4_witness(a):
    n = len(a)
    for u, v in combinations(range(n), 2):
        common = [w for w in range(n) if a[u][w] and a[v][w]]
        if len(common) >= 2:
            return (u, common[0], v, common[1])
    return None


def direct_witness(a):
    for p in permutations(range(len(a)), 4):
        if all(a[p[i]][p[(i + 1) % 4]] for i in range(4)):
            return p
    return None


def verify_cycle(a, witness):
    return (len(witness) == 4 and len(set(witness)) == 4
            and all(0 <= v < len(a) for v in witness)
            and all(a[witness[i]][witness[(i + 1) % 4]]
                    for i in range(4)))


def pair_certificate(a):
    return [(u, v, sum(a[u][w] * a[v][w] for w in range(len(a))))
            for u, v in combinations(range(len(a)), 2)]



def verify_free(a, certificate):
    pairs = set(combinations(range(len(a)), 2))
    values = {(u, v): c for u, v, c in certificate}
    if len(values) != len(certificate) or set(values) != pairs:
        return False
    neighbors = [{v for v, entry in enumerate(row) if entry} for row in a]
    return all(values[u, v] == len(neighbors[u] & neighbors[v]) <= 1
               for u, v in pairs)


def isomorphic(a, b):
    da, db = list(map(sum, a)), list(map(sum, b))
    if sorted(da) != sorted(db):
        return False
    for p in permutations(range(len(a))):
        if all(da[u] == db[p[u]] for u in range(len(a))):
            if all(a[u][v] == b[p[u]][p[v]]
                   for u, v in combinations(range(len(a)), 2)):
                return True
    return False


def reiman_floor(n):
    if n == 0:
        return 0
    return (n + isqrt(n * n * (4 * n - 3))) // 4


def run():
    records, summaries = [], []
    for n in range(6):
        buckets = defaultdict(list)
        feasible = []
        for mask in range(1 << (n * (n - 1) // 2)):
            a = matrix(n, mask)
            w, independent = c4_witness(a), direct_witness(a)
            assert (w is None) == (independent is None)
            if w is not None:
                assert verify_cycle(a, w)
            cert = pair_certificate(a) if w is None else list(w)
            if w is None:
                assert verify_free(a, cert)
                feasible.append(mask)
            rep = canonical(a)
            assert isomorphic(a, matrix(n, rep))
            buckets[rep].append(mask)
            records.append({'n': n, 'mask': mask, 'canonical': rep,
                            'edges': mask.bit_count(), 'c4_free': w is None,
                            'certificate': cert})
        reps = sorted(buckets)
        for i, x in enumerate(reps):
            for y in reps[i + 1:]:
                assert not isomorphic(matrix(n, x), matrix(n, y))
        for rep, bucket in buckets.items():
            a = matrix(n, rep)
            encodings = [encode(a, p) for p in permutations(range(n))]
            orbit = set(encodings)
            automorphisms = sum(m == rep for m in encodings)
            assert orbit == set(bucket)
            assert len(orbit) * automorphisms == factorial(n)
        best = max(m.bit_count() for m in feasible)
        winners = [m for m in feasible if m.bit_count() == best]
        free_reps = [r for r in reps if c4_witness(matrix(n, r)) is None]
        win_reps = [r for r in free_reps if r.bit_count() == best]
        assert best == reiman_floor(n)
        if n >= 3:
            assert all(n - 1 in map(sum, matrix(n, m)) for m in winners)
        summaries.append({'n': n, 'labeled': 1 << (n * (n - 1) // 2),
                          'unlabeled': len(reps), 'free_labeled': len(feasible),
                          'free_unlabeled': len(free_reps), 'maximum': best,
                          'maximizers_labeled': len(winners),
                          'maximizers_unlabeled': len(win_reps)})
    assert direct_witness(matrix(4, 63)) is not None
    assert not verify_cycle(matrix(4, 63), (0, 1, 1, 3))
    edges = [(1, 2), (1, 4), (1, 6), (1, 8), (2, 4), (2, 5),
             (3, 4), (3, 7), (5, 7), (6, 7), (6, 8)]
    a = [[0] * 8 for _ in range(8)]
    for u, v in edges:
        a[u - 1][v - 1] = a[v - 1][u - 1] = 1
    assert c4_witness(a) is None and direct_witness(a) is None
    assert len(edges) == 11 > 7 + 7 // 2
    assert verify_free(a, pair_certificate(a))
    assert not verify_free(a, pair_certificate(a)[:-1])
    payload = {'parameters': {'max_n': 5, 'edge_order': 'lexicographic',
                             'containment': 'non-induced C4'},
               'summaries': summaries, 'records': records,
               'counterexample': {'n': 8, 'edges_one_based': edges,
                                  'pair_certificate': pair_certificate(a)}}
    data = json.dumps(payload, sort_keys=True, separators=(',', ':')) + '\n'
    Path('extremal-data.json').write_text(data, encoding='utf-8')
    print('Python:', sys.version.split()[0])
    for row in summaries:
        print(json.dumps(row, sort_keys=True))
    print('records:', len(records))
    print('SHA256:', hashlib.sha256(data.encode()).hexdigest())


if __name__ == '__main__':
    run()

The exact summaries, with labeled counts followed by unlabeled counts, are:

• $n=0$: all graphs $1,1$; avoiding graphs $1,1$; maximum 0; maximizers $1,1$.
• $n=1$: all graphs $1,1$; avoiding graphs $1,1$; maximum 0; maximizers $1,1$.
• $n=2$: all graphs $2,2$; avoiding graphs $2,2$; maximum 1; maximizers $1,1$.
• $n=3$: all graphs $8,4$; avoiding graphs $8,4$; maximum 3; maximizers $1,1$.
• $n=4$: all graphs $64,11$; avoiding graphs $54,8$; maximum 4; maximizers $12,1$.
• $n=5$: all graphs $1{,}024,34$; avoiding graphs $548,18$; maximum 6; maximizers $15,1$.

There are 1,100 input records in total. Do not divide labeled counts by $n!$: different graphs have different automorphism groups. For example, the five-vertex bowtie has eight automorphisms, so its class has $5!/8=15$ labeled realizations. The four-vertex triangle with one pendant vertex has two automorphisms, giving $4!/2=12$.

Brute-force canonicalization costs $O(n!n^2)$ per input, in addition to the independent checks. The two containment tests cost at most $O(n^3)$ and $O(n^4)$ per input respectively. The program stores all labeled records, so its memory is exponential in $\binom n2$, with an additional polynomial factor for certificates. Raising the range is a new computation, not a harmless change to a printed bound. For larger projects, study McKay and Piperno's primary Practical graph isomorphism, II; do not claim that the teaching enumerator has the performance of nauty or Traces.

Exercise: how many labeled realizations does a five-vertex star have? Hint: its four leaves can be permuted freely. Solution: its automorphism group has size $4!$, so there are $5!/4!=5$ realizations, one for each center. This differs from the bowtie's orbit size despite the common vertex count.

Testing forbidden configurations

Two distinct vertices $u,v$ have a codegree equal to the number of their common neighbors. A graph contains $C_4$ if and only if some pair has codegree at least two. Two distinct common neighbors $x,y$ give the cycle $u,x,v,y,u$; simplicity ensures all four vertices are distinct. Conversely, opposite vertices in any four-cycle share its other two vertices. Chords do not affect this equivalence.

The first detector finds such a pair and returns the four cyclically ordered vertices. The independent detector tests all ordered injections of four vertices and checks the four required edges directly. They use different logical formulations, and the program compares their decisions on every input. A rejecting certificate is the four-vertex witness; a consumer verifies distinctness, range, and all four edges without trusting the detector.

An accepting certificate lists, for every unordered vertex pair, its exact codegree. The independent validator recomputes neighbor intersections, requires complete pair coverage without duplicate entries, checks every supplied value, and requires all values to be at most one. Omitting inconvenient pairs therefore does not create a valid certificate. Unlike a rejecting witness, this is an absence certificate whose verification examines the whole graph; it is not a constant-size proof of avoidance.

Worked acceptance: in the bowtie, pair $\{1,2\}$ has the common neighbor 0, and pair $\{1,3\}$ also has only common neighbor 0. Pair $\{0,1\}$ has only common neighbor 2. The analogous pairs behave the same way; no pair reaches two. Worked rejection: in the four-cycle, vertices 0 and 2 have common neighbors 1 and 3, producing witness $(0,1,2,3)$.

Positive and negative controls matter. The program confirms that complete graph $K_4$ is rejected, rejects a malformed witness with a repeated vertex, and rejects an accepting certificate missing a pair. A real dataset consumer should also validate that its input adjacency matrix is symmetric, binary, and has zero diagonal; this program constructs matrices satisfying those conditions from masks rather than reading arbitrary matrices.

Exercise: does the diamond graph $K_4$ with one edge removed avoid the forbidden graph? Hint: inspect the two vertices incident with the missing edge. Solution: no. They have the other two vertices as common neighbors and hence form a four-cycle with them. An induced-cycle detector would incorrectly accept this instance for our task.

Extremal constructions and structural patterns

The small extremal representatives are the empty graphs at orders zero and one, the edge at order two, the triangle at order three, the triangle with a pendant vertex at order four, and the bowtie at order five. Their edge counts are $0,0,1,3,4,6$. The exhaustive class check gives one maximizing isomorphism class at each of these orders. This classification is a finite result; uniqueness at larger orders has not been established by this experiment.

Here is the independent benchmark proof. In a $C_4$-free graph, count paths of length two by their middle vertex. Each endpoint pair can have at most one common neighbor, so

$$\sum_v\binom{d(v)}2\le\binom n2.$$

Let $m$ be the number of edges and $\bar d=2m/n$, for $n\ge1$. Cauchy–Schwarz implies $\sum_vd(v)^2\ge n\bar d^2$, giving $\bar d(\bar d-1)\le n-1$. Solving this quadratic and using $m=n\bar d/2$ proves the stated upper bound. The program computes its integer floor without floating-point rounding by using the integer square root of $n^2(4n-3)$.

At orders one through five, the benchmark ceilings are $0,1,3,4,6$, exactly the attained counts. Thus each maximum has a mathematical upper bound and an explicit construction, independently of exhaustive enumeration. Matching the ceiling in these orders does not imply it will always be attained.

The maximizers suggest a shared shape: a vertex adjacent to every other vertex, called a universal vertex, with a matching among its neighbors. This is an empirical pattern to investigate, not a general stability theorem. A stability theorem must specify its allowed orders, density threshold, and conclusion about distance or containment. Similar-looking small maximizers do not supply these quantifiers.

Literature check, 13 October 2026: Firke, Kosek, Nash, and Williford's primary Extremal Graphs Without 4-Cycles studies exact results at orders $q^2+q$ for even $q$, connected with polarity constructions. He, Ma, and Yang's Some exact results on 4-cycles: stability and supersaturation, published in 2023, gives specialized stability results at orders $q^2+q+1$ for sufficiently large even $q$. These established results concern particular hypotheses and geometric constructions, not universal-vertex stability for arbitrary orders. Their advanced proofs are outside this capstone, and no best-current global classification is claimed here.

Exercise: can the balanced complete bipartite graph $K_{2,3}$ serve as a feasible six-edge construction at order five? Solution: no. The two vertices in its smaller part have three common neighbors. It is triangle-free, but our forbidden graph is $C_4$, demonstrating why a construction from another extremal problem must be revalidated.

A conjecture with an honest proof boundary

Initial conjecture, now refuted: for every $n\ge3$, every maximizing $C_4$-free graph has a universal vertex. The experiment supports this only through order five. We first prove an exact result in the proposed structural class, then search beyond the original range without pretending to enumerate all larger graphs.

Complete restricted theorem: among $C_4$-free graphs on $n\ge1$ vertices having a specified universal vertex, the maximum edge count is

$$n-1+\left\lfloor\frac{n-1}{2}\right\rfloor.$$

To prove it, remove the universal vertex $v$. If some remaining vertex $x$ has distinct remaining neighbors $a,b$, then $v,a,x,b,v$ is a four-cycle. Thus the remaining graph has maximum degree at most one: it is a matching together with isolated vertices. It has at most $\lfloor(n-1)/2\rfloor$ edges, in addition to the $n-1$ edges from $v$.

Conversely, adjoining a universal vertex to any matching and isolated vertices gives a $C_4$-free graph. A four-cycle not using $v$ would have to lie in a matching, which is impossible. A four-cycle using $v$ would require a two-edge path in the remaining graph, also impossible. A maximum matching attains the bound, completing both directions. This proves the structural claim and its maximum in an infinite restricted family; it does not prove that the unrestricted optimizer belongs to that family.

Counterexample to the general extrapolation: use vertices $1,\ldots,8$ and edges

$$\{12,14,16,18,24,25,34,37,57,67,68\},$$

where each two-digit string denotes one edge. There are eleven edges. The neighbor sets, in vertex order, are $\{2,4,6,8\}$, $\{1,4,5\}$, $\{4,7\}$, $\{1,2,3\}$, $\{2,7\}$, $\{1,7,8\}$, $\{3,5,6\}$, and $\{1,6\}$. Every pair has at most one common neighbor; both containment detectors and the complete pair certificate verify avoidance. A universal-vertex graph at this order has at most $7+3=10$ edges by the restricted theorem.

Consequently $\operatorname{ex}(8,C_4)\ge11$, and no maximizing graph at order eight can have a universal vertex. We do not need to prove that this eleven-edge witness is itself extremal to refute the conjecture. This is a useful proof boundary: a lower-bound witness above the entire conjectured class's ceiling excludes that class from the optimum.

The witness can also be reconstructed systematically. On the seven nonzero binary three-vectors, join distinct vectors when their dot product is zero over the two-element field. Encoding these vectors by integers 1 through 7 gives the first nine edges above. Distinct nonzero vectors give independent orthogonality equations, so their common orthogonal subspace has dimension one, containing just one nonzero vector; common-neighbor counts are at most one. Vertices 1 and 6 have no common neighbor in this graph. Add vertex 8 adjacent to both. This creates one new common neighbor for that pair, and any pair involving 8 still has at most one common neighbor, because no old vertex was adjacent to both 1 and 6. Thus the extension remains $C_4$-free. This is a small polarity-type construction, not a claimed novel discovery.

Exercise: why is a nonuniversal eleven-edge witness alone insufficient to refute “every maximizer is universal” without the restricted theorem? Solution: the witness might be nonextremal, while a denser universal graph might exist. The restricted upper bound eliminates that possibility. Update the conjecture log to “refuted at order eight”; do not retain an unqualified universal claim in the final report.

Extremal discovery report and assessment

The completed report should state the graph class and non-induced convention first, then give the encoding, canonicalization procedure, independent validators, exact summaries, benchmark proof, constructions, conjecture history, restricted theorem, and counterexample. The reference result is exact extremal counts through order five with independently checked classes; the broader conjecture is disproved, and the universal-vertex subclass is solved for all orders. The exact unrestricted maximum at order eight is not established by the presented witness and is not needed for this conclusion.

The complete panel supplies the executable source and writes the exact dataset. Each labeled record stores n, mask, canonical, edges, c4_free, and certificate. An accepted record uses the complete codegree list; a rejected one uses an ordered cycle witness. The counterexample record separately marks its edge labels as one-based, whereas the stored pair certificate uses the zero-based matrix indices. Preserving this distinction avoids a common reproducibility error.

A project submission must include extremal_lab.py, the generated extremal-data.json, the interpreter version and invocation, the printed summaries, and the written mathematical arguments. The reference dataset SHA-256 is c53291f6b87a08259e94026532472805ec82f99a63c5d637747c64b0eb15d2be. It identifies the deterministic sorted JSON bytes, including the final newline. A matching checksum supports byte-level reproduction; the validators and proofs support the mathematics.

State limitations explicitly: the main exhaustive range ends at five; the eight-vertex object is a targeted construction, not an eight-vertex census; brute-force isomorphism testing scales factorially; and the reported similarity of small maximizers is not a stability theorem. Current primary literature must be inspected before proposing a novel remaining question. No new open problem or improved published bound is claimed by this educational reproduction.

An application is the design of incidence networks where any pair of vertices may share at most one neighbor. In a bipartite representation of objects and resources, a four-cycle means two objects share two resources. A checked codegree certificate can verify the desired overlap restriction. Our experiment permits triangles and nonbipartite graphs, so applying its exact maxima to a bipartite engineering design requires a separately restricted search and proof.