Erdős problem 1035 — wave 8a

Date of live-page check: 2026-07-28 UTC.

Result in one paragraph

The live-page gate passed: the problem is OPEN, with **0 claimed

proofs**, no current worker, and no user marked as interested in

collaborating. I did not solve the uniform constant-\(c\) question. I did

obtain and independently check the following concrete results. If

\(\tau_n\) is the least integer \(d\) such that every \(2^n\)-vertex graph

of minimum degree at least \(d\) contains a spanning \(Q_n\), then

The sharp \(n=3\) obstruction is the explicit 5-regular graph

\(K_8-(C_3\sqcup C_5)\). Uniformly for \(n\geq2\), graph packing gives

The lower bound is an elementary clique-sum separator construction; the

upper bound is rigorous modulo the Kaul--Kostochka equality

classification for the Sauer--Spencer packing theorem. A standalone

standard-library checker is in

runs/erdos1035_wave8a_reverify.py; it runs in about 1.3 seconds here.

Claim labels

Every mathematical conclusion below is labelled as requested.

• (a) elementary-rigorous: a proof is included from first principles.
• (b) rigorous-modulo-named-theorem: the exact theorem and a primary

source are identified.

• (c) plausible/structural-unverified: a heuristic or an identified

possible route, not a theorem.

• (d) computational-only: established by the finite checker, not

promoted to a uniform theorem.

Step 0: authoritative live page and stop gate

The main page and its discussion thread were rendered through the Bright

Data browser path, not by direct datacenter curl.

Verbatim current statement

> Is there a constant \(c>0\) such that every graph on \(2^n\) vertices

> with minimum degree \(>(1-c)2^n\) contains the \(n\)-dimensional

> hypercube \(Q_n\)?

Live status and markers

• Status: OPEN.
• Claimed proofs: 0.
• “Currently working on this problem”: None.
• “Interested in collaborating”: None.
• “This problem looks tractable”: user RhOd5.
• All other displayed reaction/formalisation markers were None.

Thus the mandatory stop condition did not fire.

Results and related questions displayed on the page

The page cites Erdős [Er93, p. 345]. It says that, if the conjecture is

false, Erdős suggested:

1. estimating the least \(m>2^n\) such that an \(m\)-vertex graph of

minimum degree \(>(1-c)2^n\) must contain \(Q_n\); and

2. determining those \(u_n\) for which minimum degree

\(>2^n-u_n\) forces \(Q_n\).

It also points to problem 576 for the edge-extremal question.

All six comments (faithful summary)

All six are dated 14 September 2025, and the page explicitly warns that

comments are not verified.

1. Zach Hunter (09:25) says problem 181 seems more relevant than 576;

naive dependent random choice suggests roughly

\(2^n(1-c)^{-n}\) ambient vertices, and he suggests that

Tikhomirov's methods improve the constant in the exponent.

2. Zach Hunter (10:16) describes a “blow-up case”: start from a fixed

graph \(H_0\) of minimum degree \(>m_0/2\), take a Hamilton cycle by

Dirac, and map cube layers cyclically around it, with asymptotically

balanced fibres.

3. Zach Hunter (10:20) asks whether a quantitatively strong blow-up

lemma might give an ambient order \((1+o(1))2^n\) in general.

4. Thomas Bloom (10:24) asks which blow-up lemma is meant.

5. Zach Hunter (12:18) clarifies that he means the regularity/blow-up

lemma for spanning or nearly spanning bounded-degree embeddings, and

speculates that bipartiteness/pathwidth might permit good enough

dependencies.

6. Thomas Bloom (12:54) acknowledges that clarification.

None is a solution claim or a current-work marker.

Literature audit

What was verified

• Original citation. The publisher confirms P. Erdős,

“Some of my favorite solved and unsolved problems in graph theory,”

Quaestiones Mathematicae 16(3) (1993), 333--350,

DOI 10.1080/16073606.1993.9631741.

The article is paywalled, so I could not independently inspect p. 345.

I therefore take the exact statement above from the authoritative live

page and do not attribute any further wording to the original paper.

• Packing theorem and equality cases. Sauer and Spencer's theorem

says that two \(N\)-vertex graphs of maximum degrees

\(\Delta_1,\Delta_2\) pack when

\(2\Delta_1\Delta_2

under \(2\Delta_1\Delta_2\leq N\), non-packing occurs exactly when one

graph is a perfect matching and the other is either

\(K_{N/2,N/2}\) with \(N/2\) odd or contains \(K_{N/2+1}\).

I checked Theorems 1.1 and 1.2 in their primary paper,

H. Kaul and A. Kostochka, “Extremal Graphs for a Graph Packing

Theorem of Sauer and Spencer,” *Combinatorics, Probability and

Computing* 16 (2007), 409--416,

DOI 10.1017/S0963548306007929.

• Random-host comparison. Oliver Riordan proved that for fixed

\(p>1/4\), the random graph on \(2^d\) vertices asymptotically almost

surely contains a spanning \(Q_d\). This is an average-case result,

not an adversarial minimum-degree result:

“Spanning Subgraphs of Random Graphs,” *Combinatorics, Probability

and Computing* 9 (2000), 125--148,

DOI 10.1017/S0963548399004150.

• The Tikhomirov result mentioned indirectly in the comments.

Theorem 1.1 of K. Tikhomirov,

arXiv:2208.14568v3, says that a

bipartite graph with both parts of size at least

\(2^{2n-cn}\) and density at least \(1/2\) contains \(Q_n\), for a

universal \(c>0\) (the paper gives \(c=0.03656\) for sufficiently

large \(n\)). This yields a Ramsey bound but has exponentially more

vertices than the present \(2^n\)-vertex host. (b)

• Bandwidth machinery. The bandwidth theorem of Böttcher,

Schacht and Taraz requires a fixed maximum-degree bound \(\Delta\):

“Proof of the bandwidth conjecture of Bollobás and Komlós,”

Mathematische Annalen 343 (2009), 175--205,

DOI 10.1007/s00208-008-0268-6.

The arrangeable blow-up extension likewise fixes the arrangeability

parameter \(a\); see Böttcher, Kohayakawa, Taraz and Würfl,

arXiv:1305.2059,

DOI 10.1137/13093827X.

Search miss, stated narrowly

Exact-statement searches found the live tracker but no paper claiming

this minimum-degree problem solved. I also inspected the 32 works that

OpenAlex currently records as citing Er93; their titles and indexed

abstracts did not reveal a work about this spanning-cube

minimum-degree question. This is not proof of absence: citation

indexes are incomplete, the original paper poses many unrelated

problems, and the live page itself warns that literature may be

missing. I therefore make no “complete literature” claim.

1. Packing reformulation

Put \(N=2^n\) and \(F=\overline G\). A spanning copy of \(Q_n\) in

\(G\) is exactly a bijection

such that no cube edge \(xy\) is sent to an edge \(f(x)f(y)\) of

\(F\). In graph-packing language, \(Q_n\) and \(F\) pack. (a)

Also,

This isolates the issue: the open problem asks whether \(Q_n\) packs

with every \(N\)-vertex forbidden graph of maximum degree at most

\(cN+O(1)\), for some fixed \(c>0\).

2. A from-scratch strict packing lemma

Lemma. If \(A,B\) are \(N\)-vertex graphs and

\(2\Delta(A)\Delta(B)(a)

Proof. Choose a bijection \(f:V(A)\to V(B)\) minimizing the number

of conflicts \(xy\in E(A)\) for which \(f(x)f(y)\in E(B)\). Suppose

\(xy\) is a conflict. Swap the images of \(x\) and a vertex \(z\).

The swap creates no conflict at an edge incident with \(x\) provided

a set of size at most \(\Delta(A)\Delta(B)\). It creates no conflict

at an edge incident with \(z\) provided

another set of size at most \(\Delta(A)\Delta(B)\). Fewer than \(N\)

vertices are excluded, so a suitable \(z\) exists. The first condition,

with \(a=y\), removes the chosen conflict; all other changed edges are

nonconflicts. This contradicts minimality. \(\square\)

For \(A=Q_n\), this gives the elementary condition

3. Including equality, and the uniform upper bound

Kaul--Kostochka permits equality except for the classified pairs.

For \(n\geq2\), \(Q_n\) is not a perfect matching. If the other graph

is a perfect matching, the exceptional partner is still not \(Q_n\):

• \(Q_2=K_{2,2}\), but \(N/2=2\) is even; and
• for \(n\geq3\), \(Q_n\neq K_{N/2,N/2}\), and its bipartiteness gives

clique number \(2\), so it cannot contain \(K_{N/2+1}\).

Consequently

This is (b), with all exception checks (a).

Let

Equations (2) and (4) prove

In the live page's strict \(>2^n-u_n\) normalization, (5) says that

the integer sequence \(u_n=D_n+2\) works. This is

\(\Theta(2^n/n)\), not a constant proportion of \(2^n\), so it does

not settle the stated question. (b)

4. Uniform separator obstruction

The cube \(Q_n\) is \(n\)-vertex-connected. Here is a short induction.

View \(Q_n\) as two \(Q_{n-1}\) facets joined by a perfect matching.

After deleting at most \(n-1\) vertices, either both facets lose at most

\(n-2\) vertices and are connected by induction, with an undeleted

matching edge between them, or one facet loses all \(n-1\) deleted

vertices and every surviving vertex there has its matching edge into

the intact facet. The small bases are immediate. (a)

Now take disjoint nonempty sets \(A,B,S\), where

and let the host consist of the two cliques on \(A\cup S\) and

\(B\cup S\), with no \(A\)-\(B\) edge. Removing \(S\) disconnects the

host, so it cannot have a spanning \(n\)-connected subgraph and hence

cannot contain a spanning \(Q_n\). Its minimum degree is

This proves the lower half of (1). (a)

5. Exact cases \(n\leq3\)

For \(n=1\), the empty two-vertex graph is the sharp obstruction, so

\(\tau_1=1\). For \(n=2\), the separator construction is \(2K_2\),

of minimum degree 1, while (5) gives \(\tau_2\leq2\). Thus

\(\tau_2=2\). (a), (b)

For \(n=3\), (5) gives \(\tau_3\leq6\). To show sharpness, let

Every vertex of \(G\) has degree \(7-2=5\). If \(G\) contained a

spanning \(Q_3\), then \(H\) would be a spanning subgraph of

\(\overline{Q_3}\).

Split \(Q_3\) by parity. Within each parity class,

\(\overline{Q_3}\) induces \(K_4\); between the two classes its edges

are exactly the four antipodal pairs, a perfect matching. Every

triangle of \(\overline{Q_3}\) lies inside one \(K_4\), since a triangle

crossing the split would require two edges of that matching at one

vertex. After a triangle is removed from one \(K_4\), the five

remaining vertices are one vertex on that side and all four on the

other. The singleton has at most one neighbour among the other four,

so it cannot lie on a spanning \(C_5\). Hence

\(C_3\sqcup C_5\not\subseteq\overline{Q_3}\), \(G\) is \(Q_3\)-free,

and

This obstruction and proof are (a).

The checker independently enumerates all 840 labelled copies of

\(Q_3\), confirms that none avoids \(C_3\sqcup C_5\), and enumerates

all 764 labelled matchings on eight vertices to confirm the upper

case directly. (d)

6. The concrete \(n=4\) regime

The clique-sum construction has \(|S|=3\), \(|A|=6\), \(|B|=7\), and

minimum degree 8, so \(\tau_4\geq9\). Equation (5) has

\(D_4=\lfloor16/8\rfloor=2\), so \(\tau_4\leq13\). Therefore

The lower bound is (a) and the upper bound is (b).

There is also an independent finite check of the upper bound. Every

16-vertex graph of maximum degree at most two is uniquely a multiset

of paths (including isolated vertices) and cycles. The checker

generates all 971 such isomorphism types from this decomposition and,

by a from-scratch bijective backtracker, embeds each one in

\(\overline{Q_4}\). This independently verifies that every host of

minimum degree at least 13 contains \(Q_4\). (d)

7. Why the advertised blow-up machinery currently stops

Ordering the cube by Hamming layers gives

Thus the cube has the needed sublinear bandwidth, but its maximum

degree is \(n=\log_2 N\), whereas the classical bandwidth theorem fixes

\(\Delta\) before \(N\to\infty\). (a) for the bandwidth estimate;

(b) for the theorem's scope.

The arrangeable blow-up lemma allows growing maximum degree, but fixes

the arrangeability parameter \(a\). The cube family cannot satisfy

such a fixed bound. Recall that an ordering \(v_1,\ldots,v_N\) is

\(a\)-arrangeable when, for every \(i\), the union of the earlier

neighbours of the later neighbours of \(v_i\) has size at most \(a\).

In fact,

To prove this, fix any vertex ordering, orient every cube edge forward,

and let \(d^-(v)\) be the number of earlier neighbours of \(v\).

There are

wedges whose middle vertex is later than both endpoints. Assign each

wedge to its later endpoint \(u\). The earlier endpoint belongs to

the set counted by arrangeability at \(u\). Any endpoint pair in a

cube has at most two common neighbours, so each counted earlier

endpoint accounts for at most two wedges. Hence \(W\leq2Na\), proving

(7). (a)

The precise missing ingredient suggested by the comments is therefore

not merely “apply the blow-up lemma.” One needs a cube-specific

spanning embedding/blow-up statement that simultaneously:

1. tolerates degree \(\log_2 N\) and at least

\(\Omega((\log N)^2)\) arrangeability;

2. keeps its regularity/superregularity parameters uniform as

\(N\to\infty\); and

3. balances and absorbs every vertex, rather than producing only a

nearly spanning cube.

That statement is the exact unproved bridge between the layer-to-cycle

homomorphism in the page comments and a proof of the original

constant-\(c\) assertion. (c) as a proposed route; the failure of

the cited off-the-shelf hypotheses is (a)/(b).

8. Reproduction and computation boundary

Run:

python runs/erdos1035_wave8a_reverify.py

Observed on this VM:

elapsed=1.26 sec maxrss=15592 KB
PASS: direct cube construction and edge/degree counts (n=1..8)
PASS: exact thresholds t_1=1, t_2=2, t_3=6; Q3 copies=840, 8-vertex matchings=764
PASS: K8-(C3 disjoint-union C5) is 5-regular and Q3-free
PASS: clique-sum separator degrees n=1:delta=0, n=2:delta=1, n=3:delta=4, n=4:delta=8, n=5:delta=17, n=6:delta=33, n=7:delta=66, n=8:delta=130
PASS: packing-bound arithmetic n=2:D=1,t<=2, n=3:D=1,t<=6, n=4:D=2,t<=13, n=5:D=3,t<=28, n=6:D=5,t<=58, n=7:D=9,t<=118
PASS: cube codegree<=2 (n=1..8), with exact small arrangeabilities a(Q1)=1, a(Q2)=2, a(Q3)=3
PASS: all 971 max-degree<=2 types on 16 vertices embed in complement(Q4), independently certifying t_4<=13

No external Python package, SAT solver, or graph catalogue is used by

the checker.

To improve (6) by direct enumeration, the next unresolved layer is all

16-vertex forbidden graphs of maximum degree at most three. A

read-only pilot with nauty-geng -u -D3 16 counted 6,553,568 unlabeled

types in 41.68 seconds. The current pure-Python embedding routine

processed a 10,000-type sample at about 8,100 types/second, projecting

roughly 13.5 minutes or 0.23 core-hours for that layer alone

(approximately USD 0.01 at USD 0.05/core-hour). I did not run it

because it exceeds the requested few-CPU-minute budget, and even a

complete positive check at degree three would leave degrees four,

five, and six before \(\tau_4\) is exact. The clean exact finite task is:

for each \(k=3,4,5,6\), decide whether an \(H\) with

\(\Delta(H)\leq k\) exists that does not embed in

\(\overline{Q_4}\), preferably with a checkable SAT/DRAT certificate.

PARTIAL: Exact thresholds tau_1=1, tau_2=2, tau_3=6, the bound 9<=tau_4<=13, and a uniform O(2^n/n) deletion guarantee are verified; the fixed-positive-c problem remains open at a quantified cube-specific blow-up lemma.