25 October 2026. Primary researcher. Working proof, not yet publication acceptance.

Scope: finite simple undirected graphs. A partition has TWO NONEMPTY parts.
Target: a quantitative refinement of Lin--Zeng arXiv:2610.19014v1, not a
solution for all degrees and not a claim to have discovered the r=5,8 cases.

Proposed theorem: if r is 5 or 8 and an r-regular graph has at least 500000
vertices, every minimum bisection has a ceil(r/2)-cohesive set in EACH side.
Consequently it has an internal partition. The reference threshold is 10^7.

1. Bisection reduction (reconstructing Lin--Zeng Lemma 2.2)

Set k=ceil(r/2), p=r-k+1=floor(r/2)+1, q=r-2k+2. Suppose a side B of a
minimum bisection (A,B) has empty k-core. Put a=|A|, b=|B|, N=a+1, c=cut.
B is (k-1)-degenerate, so c >= q*b+k(k-1). Swapping u in A and v in B gives
d_A(u)+d_B(v)+1_uv >= r. For a minimum-degree vertex v in B, summation gives
c <= a*delta_B+r-delta_B. If delta_B<=k-2, this contradicts the lower bound:
for r=5, a=b and c<=b+4<b+6; for r=8, c<=2b+8<2b+12.
Thus delta_B=k-1. Choose v1 of that degree and H=G[A union {v1}]. Then
p<=d_H<=r<=p+3. Also 2e(H)=r*a-c+2p; for r=5 this is <=4a, for r=8 it is
<=6a+2(a-b)-2<=6a. In both cases 2e(H)<=(p+1)N.

Choose a full (k-1)-degeneracy order v1,...,vb for B. Move its first t
vertices into A. The cut is at most c-q*t. Moving any t-set S back to B
gives another bisection; the additional cut change is
2 sum_{v in S} d_{A_t}(v)-r*t-2e(S). Therefore
e(S)<=sum_{v in S}(d_{A_t}(v)-p).
For X_L=union_{i=2}^L (N_G(vi) intersect V(H)), |X_L|<=r(L-1), and all
nonempty S subset V(H)\X_L of size <=L obey e_H(S)<=sum(d_H(v)-p).

Important source transcription: use c-q*t, not c+q*t. The PDF v1 has a
sign mismatch and an ensuing coefficient typo in its displayed derivation.
The corrected calculation above proves the intended lemma. For r=8 one
must assume absence of a k=4 core, not absence of a p=5 core. These repairs
do not claim a counterexample to the reference's stated main theorem.

2. THREE deletion rounds, extending the reference's two-round count

Let H satisfy p<=d<=p+3 and 2e<=(p+1)N, p>=3. Let X have size x. Assume
e(S)<=sum_{v in S} w(v), w(v)=d_H(v)-p, for every S outside X of size<=53.
Delete in parallel the outside-X vertices of current degree p, three times,
calling these independent layers P0,P1,P2, and retain X throughout.

Witness induction: a vertex in Pj has exactly w(v)<=3 neighbors in earlier
layers. Recursively include all these predecessors. Its predecessor-closed
witness has at most 1+3+...+3^j vertices (1,4,13 for j=0,1,2) and exactly
sum w internal edges: every predecessor edge is counted at its later end,
and there are no edges within a layer. Two adjacent layer-j centers would
give a violating union of size <=2(1+3+...+3^j)<=26, proving independence.
If a surviving outside-X vertex had degree<p after round j, attach it to
w(v)+1<=4 deleted-neighbor witnesses. The union is predecessor-closed
apart from that vertex and has size <=1+4(1+3+...+3^j)<=53. It has more
edges than total weight, impossible. Thus outside-X degrees remain >=p.
Induction is ordered: earlier-layer independence first; establish current
layer independence; then the next surviving minimum-degree condition.

Let Qj be the total deleted before layer j, Q0=0. Every deleted vertex has
current degree exactly p and each layer is independent, hence e(H_j)=e(H)-pQj.
The (p+1)-degree deficit in H_j is at least (p-1)Qj. Outside X only Pj can
contribute positively, each by 1; X contributes at most (p+1)x. Thus
Q_{j+1} >= p Qj-(p+1)x. Moreover Q1>=n0-x, where n0 counts original degree p.
Consequently Q3 >= p^2 n0-(2p^2+2p+1)x.
After three rounds the surviving minimum degree off X gives Q3<=N/p+x.
Therefore n0 <= N/p^3 + [2+2/p+2/p^2]x.
This equals 2p/(p-1)-2/((p-1)p^2) in the bracket.

Let D be the original degree-(p+1) vertices, and nj count degree p+j.
The average-degree hypothesis says n0>=n2+2n3. Count D's incident edges:
e(D)-|D| >= (p-1)N/2 - (2p-1)n0/2 - (2p+1)n2/2 - (p+1)n3
           >= (p-1)N/2 - 2p n0
           >= [(p-1)/2-2/p^2]N - [4p+4+4/p]x.
For p=3 this is (7/9)N-(52/3)x; for p=5 it is (48/25)N-(124/5)x.

3. Small surplus set (Lin--Zeng Lemma 3.2)

For a graph F on at most N vertices, maximum degree d, if
e(F)-|V(F)| > N^2/ell^2 (integer ell>=2), there exists S with
|S|<=2d*ell and e(S)>|S|. This is a reference lemma, not claimed new.
Its proof partitions large components into connected chunks of orders
ell through d*ell. In the absence of the asserted S, each chunk has at most
as many edges as vertices, and at most two edges join any two chunks.
There are at most N/ell chunks; this bounds total edge surplus by N^2/ell^2.
Small components have nonpositive surplus and can be discarded.

4. Explicit constants, with exact rational margins

N>=250000 and s=ceil(sqrt(N)). Apply section 2 using X_53, whose size is
at most 52r. This gives e(D)-|D| >= a_p*N-C_p, with
(r,p,a_p,C_p)=(5,3,7/9,13520/3) or (8,5,48/25,51584/5).

For r=5 take ell=2s, T=8ell=16s. For r=8 take ell=ceil(5s/4), T=12ell.
Both T>=53 and T<=b: T<=16s+9 and b>=N-2; since
s<=sqrt(N)+1<=N/500+1, 16s+9<=4N/125+25<=N-2.

Remove D intersect X_T, setting F=H[D\X_T]. Each removed vertex reduces
e-|V| by at most p. Hence e(F)-|V(F)|>=a_p*N-C_p-pr(T-1).

r=5: T-1<=16s and N^2/ell^2<=N/4. The surplus margin is at least
(19/36)N-240s-13520/3
 >= (43/900)N-14240/3
 >= 64780/9 >0 at N=250000. (Exact arithmetic must be independently checked.)

r=8: T-1<=15s+8 and N^2/ell^2<=(16/25)N. The surplus margin is at least
(32/25)N-600s-320-51584/5
 >= (2/25)N-56184/5
 >= 43816/5 >0 at N=250000.

Section 3 now produces S outside X_T with |S|<=T and e(S)>|S|, whereas
section 1 gives e(S)<=sum(d_H-p)=|S|, a contradiction. Each side of every
minimum bisection therefore contains a k-cohesive set.

5. Convert disjoint cores to an internal partition (known argument)

Keep one core U and the other W disjoint. Repeatedly add to U any vertex
outside U union W with at least k neighbors in U. Upon termination put all
remaining vertices in W's part. The first part has min degree k; vertices
outside it have at most k-1 neighbors there and therefore at least r-k+1>=k
in the other part (r=5 gives equality, r=8 gives 5>=4). W never moved.
Both parts are nonempty. This is known cohesive-set extension, not novelty.

6. Boundaries and failed generalizations

For r=7 the analogous upper bound on H's average degree is 6, while p+1=5;
also the minimum-degree-on-B argument does not force delta_B=k-1. For r=10
the same density mismatch occurs. Thus the argument does NOT settle those
degrees. Do not substitute them into the theorem. We have not established
the optimal finite exception threshold, nor a polynomial-time method for
finding a minimum bisection. No external or formal proof review occurred.

Before acceptance: independent rational recheck; exhaustive bounded graph
tests of the reduction and three-round lemma; render source formula pages;
bounded current-literature check; detailed adversarial audit. Original
source record stays PARTIALLY_SOLVED even if this refinement is accepted.
