Research · Extremal graph theory · ex(50; C4)

ex(50; C4): a graph with 50 vertices and 181 edges and no 4-cycle

This page presents a piece of research in extremal graph theory: a graph with 50 vertices and 181 edges that contains no cycle of length 4, hence ex(50; C4) ≥ 181. It shows the exact statement, the landscape of public values with their sources, then the whole graph, with a short program that anyone runs to recheck it.

1. The problem

A graph is C4-free when it contains no cycle of length four. Equivalently, and this is the form the board’s checker uses, no two distinct vertices have two or more common neighbours. The number ex(n; C4) is the greatest number of edges a C4-free graph on n vertices can have.

The board’s statement: “Find a C4-free graph on exactly 50 vertices with more than 179 edges.” That is: a graph on exactly 50 vertices, labelled 0 to 49, with no 4-cycle, with more than 179 edges, no loops and no repeated edges. Source: github.com/math-market/c4-free-50, file TASK.md, read on 13 Oct 2026; the checker (check.py) is published in the same repository, under the Apache-2.0 licence.

A C4-free graph may contain triangles. On the left, the diagram shows a graph with 7 vertices and 9 edges (three triangles sharing one vertex): it has no 4-cycle, and 9 is the maximum possible with 7 vertices (ex(7; C4) = 9, OEIS A006855). On the right, one more edge closes a 4-cycle: vertex c and vertex 2 then have two common neighbours.

2. The public landscape

The table gathers the public numbers around n = 50, with their source and reading date. They are the landmarks of the problem: they place the known values and say nothing about how a graph is reached.

Readings of 13 Oct 2026: board math-market/c4-free-50 (README, TASK.md, baseline.json), OEIS A006855, page by B. McKay and N. Afzaly. The OEIS upper bounds for n = 48 and n = 49 (176 and 182) equal Reiman’s bound recomputed at those values of n.

OEIS (sequence A006855) gives ex(n; C4) for n from 1 to 40, with a(40) = 127; for n from 41 to 49 it gives only ranges, for instance 174 ≤ a(49) ≤ 182; for n = 50 it gives neither a value nor a bound. The page by B. McKay and N. Afzaly lists graphs up to n = 49. The board sets the threshold at 179 and the ceiling at 187, and notes that the maximum is, to its knowledge, not published.

At the readings of 13 Oct 2026, 181 is the largest value published for n = 50 in the sources cited above (OEIS gives neither a value nor a bound for n = 50). It is not the exact value of ex(50; C4): with Reiman’s bound, it lies between 181 and 187.

3. The result

The graph has 50 vertices, labelled 0 to 49, and 181 edges. Its degrees are 7 or 8: 38 vertices of degree 7 and 12 vertices of degree 8 (sum of degrees 362 = 2 × 181). It contains no 4-cycle, hence ex(50; C4) ≥ 181.

All 181 edges are published. The file in the board’s format is c4free_n50_181.json; the same graph is given below as an adjacency list, built into the recheck program.

The checks

Four checks, replayed on 13 Oct 2026 on the graph file:

Output of the board judge on the graph:

valid: C4-free graph on 50 vertices with 181 edges
ACCEPTED: 181 > 179 — this improves on the published baseline

Output of the judge on the graph with edge (0, 4) added:

REJECTED: vertices 0 and 3 have common neighbours 4 and 10 — that is a 4-cycle 0-4-3-10-0

Recheck it yourself

The program below contains the graph. Save it in a file verifier_c4.py and run python verifier_c4.py: Python 3 is enough, with no library to install. Each line of the list starts with a vertex, followed by its neighbours with a higher number. The program recomputes the number of edges and the degrees, applies two checks of different natures, replays a canary (an edge that creates a 4-cycle, which both checks must reject) and prints the fingerprint of the rebuilt JSON file, to be compared with the one in section 3. Saveable version: verifier_c4_en.py.

# verifier_c4.py : standard library only ; python verifier_c4.py
import hashlib, itertools, json
from collections import Counter

# the graph: one line per vertex u, followed by the neighbours numbered above u (each edge appears once)
LISTE = """
0: 1 2 3 10 20 23 37
1: 2 6 8 25 29 45
2: 7 12 19 27 43
3: 4 5 10 24 31 44
4: 5 6 12 16 36 41 46
5: 7 9 22 29 47
6: 8 11 16 21 32
7: 9 11 27 30 42
8: 9 14 15 38 44 48
9: 18 20 33 34 38
10: 11 15 17 33 40 49
11: 13 21 35 40 42
12: 13 14 19 33 39 46
13: 14 18 25 31 35
14: 15 23 26 47
15: 17 28 30 36
16: 17 18 26 27 37
17: 18 19 22 45
18: 20 25 43
19: 21 22 24 38
20: 21 23 28 46
21: 24 28 47
22: 23 29 32 35 48
23: 26 32 41 42
24: 25 26 30 34 44
25: 29 30 41 49
26: 27 34 40
27: 28 31 48 49
28: 29 31 36 39
29: 39 40
30: 32 37 46
31: 32 38 45
32: 33 43
33: 34 39 49
34: 35 36 45
35: 36 37 48
36: 41 43
37: 38 39 47
38: 40 41
39: 42 44
40: 43 46
41: 42 49
42: 44 45
43: 44 47
44: 48
45: 46 47
46: 48
47: 49
48: 49
49:
"""
N = 50
E = [(int(l.split(":")[0]), int(w)) for l in LISTE.strip().splitlines() for w in l.split(":")[1].split()]
assert len(set(E)) == len(E) and all(0 <= u < v < N for u, v in E)
adj = [set() for _ in range(N)]
for u, v in E:
    adj[u].add(v); adj[v].add(u)

# check 1: no two distinct vertices have two or more common neighbours
def sans_c4_paires(adj):
    return all(len(adj[u] & adj[v]) <= 1 for u, v in itertools.combinations(range(N), 2))

# check 2, unrelated to check 1: none of the 3 possible cycles on each of the 230,300 quadruples of vertices is present
def sans_c4_quadruplets(adj):
    for a, b, c, d in itertools.combinations(range(N), 4):
        for p, q, r, s in ((a, b, c, d), (a, b, d, c), (a, c, b, d)):
            if q in adj[p] and r in adj[q] and s in adj[r] and p in adj[s]:
                return False
    return True

# canary: an edge that closes a path of length 3 creates a 4-cycle; both checks must reject it
def canari(adj):
    for u, v in itertools.combinations(range(N), 2):
        if v not in adj[u] and any(y in adj[x] for x in adj[u] for y in adj[v]):
            c = [set(a) for a in adj]; c[u].add(v); c[v].add(u)
            return (u, v), c

ok = lambda b: "no 4-cycle" if b else "4-CYCLE FOUND"
deg = dict(sorted(Counter(len(a) for a in adj).items()))
print("vertices: %d; edges: %d; degrees (degree: number of vertices): %s" % (N, len(E), deg))
r1, r2 = sans_c4_paires(adj), sans_c4_quadruplets(adj)
print("check 1 (pairs of vertices)    : %s" % ok(r1)); print("check 2 (quadruples of vertices) : %s" % ok(r2))
e, c = canari(adj)
k1, k2 = sans_c4_paires(c), sans_c4_quadruplets(c)
print("canary: added edge %s -> check 1: %s; check 2: %s" % (e, "rejected" if not k1 else "ACCEPTED (abnormal)", "rejected" if not k2 else "ACCEPTED (abnormal)"))
print("sha256 fingerprint of the graph's JSON file: %s" % hashlib.sha256(json.dumps({"n": N, "edges": [list(x) for x in E]}).encode()).hexdigest())
bon = len(E) == 181 and r1 and r2 and not k1 and not k2
print("VERIFIED: 50 vertices, 181 edges, no 4-cycle; the canary is rejected by both checks" if bon else "FAILURE")
raise SystemExit(0 if bon else 1)

This program was run on 13 Oct 2026 (Python 3.11.0rc2, python -I) on the published graph. Output obtained:

vertices: 50; edges: 181; degrees (degree: number of vertices): {7: 38, 8: 12}
check 1 (pairs of vertices)    : no 4-cycle
check 2 (quadruples of vertices) : no 4-cycle
canary: added edge (0, 4) -> check 1: rejected; check 2: rejected
sha256 fingerprint of the graph's JSON file: 47e08a82f8af0a73d81eeb4e06c726a7495711b45d0cebef8bc10f6b05a6902d
VERIFIED: 50 vertices, 181 edges, no 4-cycle; the canary is rejected by both checks

Both checks agree with the board judge and with networkx. The fingerprint rebuilt by the program is that of the file of pull request no. 6.

sha256 fingerprints

Public repository

The graph is filed on the board’s public repository: pull request no. 6 of math-market/c4-free-50, opened on 1 Oct 2026. Its file my_graph.json has the same sha256 fingerprint as the file of this page. State read on 13 Oct 2026: open, not merged, no comment and no review. The graph is published under the Apache-2.0 licence, as the board requires for submissions. The starting graph comes from a page that shows no licence.

4. What this question models

This question belongs to extremal graph theory: how many edges can a graph on n vertices have without containing a given subgraph, here the cycle on four vertices? For large n, ex(n; C4) is of order n^3/2/2: Reiman’s bound, (n/4)(1 + √(4n − 3)), is asymptotically tight (Aigner and Ziegler, as cited by OEIS).

The graphs that reach this order come from finite geometries. In a finite projective plane of order q, which has q² + q + 1 points, two points are joined when one lies on the polar line of the other: the Erdős–Rényi polarity graph has no 4-cycle, and for q = 7 it has 57 vertices and 224 edges; the board derives its threshold of 179 from it by removing 7 vertices. Füredi shows that, for q > 13, ex(q² + q + 1; C4) ≤ q(q + 1)²/2, with equality exactly for the orthogonal polarity graphs of a plane of order q (J. Combin. Theory B 68, 1996; statement restated in the introduction of arXiv:1201.4912, read on 13 Oct 2026), and Firke, Kosek, Nash and Williford prove an upper bound on ex(q² + q; C4) for q even (arXiv:1201.4912, read on 13 Oct 2026). For a value of n such as 50, which is not of the form q² + q + 1, the exact value remains to be established: the landscape of section 2 shows what is known.

Sources: github.com/math-market/c4-free-50 (README, TASK.md, check.py, baseline.json, pull request no. 6), oeis.org/A006855, users.cecs.anu.edu.au/~bdm/data/extremal.html, arXiv:1201.4912, read on 13 Oct 2026.

A research programme, an outside test

These results cover domains with nothing to do with each other: the geometry of packings (Packomania, Friedman Packing Center), space mechanics (ESA SpOC 4), number theory (IBM Ponder This) and graphs (FlyWire Codex). In each, the result is entered on a third party’s page, a table, a ranking or a list, and can be rechecked by computation: ESA evaluates each solution with its simulator, Packomania publishes the entries it accepts, IBM publishes a list of names, Friedman keeps a page that credits authors. These results belong to a single research programme: keep only what a certificate proves.

This page applies the same principle to a problem on graphs: a result whose complete list is published, a short program that anyone runs, and the judge of an outside board that accepts the graph. Here, the reader rechecks it personally.

The principle is public: every hypothesis is tested by computation and kept only if a certificate proves it. Generative AIs serve me as assistants, interchangeable ones: they propose, my AI decides, the certificate settles. The internal workings remain confidential. The results are public.

The certificate changes the nature of proof. A result can be checked without trusting whoever produced it, as a proof can be checked without knowing its author. That is what makes this page possible: you do not have to believe me, you recheck. The result is fixed by its fingerprint, which is published.

All the work runs on accessible hardware: a desktop PC, a Raspberry Pi 5 and a Raspberry Pi Pico, which also serve to check that the computation stays identical from one machine to another; occasionally, a 32-vCPU instance. The programme aims at a certifiable embedded AI, down to modest machines.

A result that is verifiable without trust, fixed and rechecked: these properties open onto the intended uses:

• certifiable embedded AI, down to modest machines;
• steering generative AIs, keeping only what is proven;
• verifiable identity for AI agents;
• audit after an incident: replaying a past decision exactly;
• reproducible science;
• an open map of certified computations: each result with its certificate, so that what is proven is not recomputed.

The research programme sets out this framework. All the results, with their sources and dates, are gathered on the Results page.