Friendly partitions

Friendly partitions

Definitions and mathematical statement

Let $G=(V,E)$ be a finite simple graph. For $v\in V$ and $X\subseteq V$, put $d_X(v)=|N_G(v)\cap X|$. A friendly, or internal, partition is a decomposition $V=A\mathbin{\dot\cup}B$ into two nonempty sets such that \[ d_A(v)\geq d_B(v)\quad(v\in A),\qquad d_B(v)\geq d_A(v)\quad(v\in B). \] The requirement that both parts be nonempty excludes the trivial partition putting every vertex on the same side. No equality of the two part sizes is required.

For an $r$-regular graph, these inequalities are equivalent to each vertex having at least $\lceil r/2\rceil$ neighbours in its own part. In particular, each induced subgraph $G[A]$ and $G[B]$ must have minimum degree at least $\lceil r/2\rceil$.

The conjecture asks whether for every fixed integer $r\geq1$ there exists an integer $N(r)$ such that every finite simple $r$-regular graph on at least $N(r)$ vertices has a friendly partition. This is the meaning of all but finitely many graphs, with exceptions counted up to isomorphism. The degree is fixed before the order grows. The threshold must work for every graph of that degree, not only almost every randomly sampled graph. Disconnected graphs are included; the difficult instances are the connected ones. The assertion is local at every vertex, not just a bound on the total number of crossing edges.

Short English statement

For each fixed degree, do all sufficiently large regular graphs split into two nonempty parts so every vertex has at least half its neighbours on its own side?

Research attempt

Scope and process.

This is a GPT-6 Astra Ultra research attempt dated 1 October 2026, using primary-source browsing and elementary mathematical checks. The canonical definition above is retained. Results below are restricted results or reductions, not a claim of a new solution to the entire catalogue question. No formal proof assistant or external mathematical referee checked this text.

Literature and plan.

Ban and Linial [S3] formulate the fixed-degree problem and prove the case of degree six. We independently establish a seed-extension lemma and a complete elementary proof for degrees one, two and three. These are restricted, known cases, not a solution for all fixed degrees. The central issue is that minimizing a cut alone admits an empty side; the seed sets below prevent precisely that degeneracy.

Two dense seeds extend to an internal partition.

Let $G$ be $r$-regular, and suppose there are disjoint nonempty vertex sets $A_0,B_0$ each inducing minimum degree at least $h=\lceil r/2\rceil$. Among partitions $V=A\mathbin{\dot\cup}B$ with $A_0\subseteq A$ and $B_0\subseteq B$, choose one minimizing the number of crossing edges. Both parts remain nonempty because of the seeds. Every seed vertex already has at least $h$ neighbours in its own part. If a nonseed vertex $v$ had more neighbours across the cut than within its own part, moving it would preserve the seed constraints and change the cut size by $d_{\rm own}(v)-d_{\rm other}(v)<0$, a contradiction. Thus every vertex satisfies the required local inequality.

For cubic graphs the seed threshold is two. A finite graph of minimum degree at least two contains a cycle: follow a maximal simple path, whose last vertex has a neighbour earlier than its predecessor. Consequently an internal partition in a cubic graph yields two vertex-disjoint cycles, one in each part. Conversely two disjoint cycles supply the seeds in the lemma. We have proved the exact criterion \[ G\text{ cubic has an internal partition} \quad\Longleftrightarrow\quad G\text{ has two vertex-disjoint cycles}. \] Chords on either cycle only add helpful internal neighbours.

Finding the two cycles except in two small connected graphs.

Assume now that $G$ is connected, simple and cubic, and let $C$ be a shortest cycle of length $g$. This cycle is chordless. Each of its vertices therefore has exactly one neighbour outside $C$, so the edge cut leaving $C$ has size $g$. If $G-V(C)$ were a forest with $c\ge1$ components, its $n-g$ vertices and $n-g-c$ edges would satisfy the degree count \[ 3(n-g)=2(n-g-c)+g,\qquad n=2g-2c<2g. \] The outside is nonempty: a cubic graph consisting of the vertices of a chordless cycle would have degree two. Hence $n\ge2g$ forces a second cycle outside $C$.

For $g\ge5$, a breadth-first count ensures $n\ge2g$. If $g=2t+1$, the rooted tree of distances through level $t$ has at least $1+3(2^t-1)$ distinct vertices. A collision would give a cycle shorter than $g$. For $t\ge2$, this quantity is at least $2(2t+1)$, starting with equality at $t=2$ and increasing thereafter. If $g=2t$, use the two trees growing from the endpoints of an edge, to depth $t-1$ on either side. There are at least $2(2^t-1)$ distinct vertices; a collision again gives a shorter cycle. For $t\ge3$ this is at least $4t=2g$. Thus the required second cycle exists in both cases.

If $g=3$, the even order of a cubic graph is at least six unless $n=4$, in which case the graph is $K_4$. If $g=4$, the even order is at least eight unless $n=6$. A triangle-free cubic graph on six vertices must be $K_{3,3}$: the three neighbours of a vertex are independent, and each must join both of the remaining two vertices to achieve degree three. The other small possibility $n=4$ is incompatible with girth four. Thus every connected simple cubic graph except $K_4,K_{3,3}$ has the desired partition. Neither exception can have two disjoint cycles, by its order and girth, so both really fail.

Low degrees and verification.

A disconnected regular graph with at least two components has an internal partition by putting whole components on opposite sides. A degree-one graph is a matching, so only $K_2$ fails. A connected degree-two graph is a cycle. For length at least four, split its cyclic order into two paths each with at least two vertices; every vertex retains a neighbour in its own part. Only the triangle fails. Accordingly $N(1)=4,N(2)=4,N(3)=8$ are valid thresholds under the catalogue's "at least" convention.

The seed argument preserves both nonempty parts at every move, and the shortest-cycle count uses simplicity to rule out shorter cycles and hidden parallel edges. The parity assertion $n$ even follows from $3n=2|E|$, not from a connectivity assumption. These checks are important at the orders where the two cubic exceptions occur.

Final status and first remaining gap.

UNRESOLVED for arbitrary fixed degree. For higher $r$, a cycle supplies only two internal neighbours and is no longer an adequate seed. The first missing step in this route is a guarantee of two disjoint induced subgraphs of minimum degree $\lceil r/2\rceil$ in every sufficiently large $r$-regular graph. The min-cut extension proves what such seeds would achieve, but does not prove that they always exist.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3156 (OPG-37163), OpenGarden collection. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, Friendly partitions. Original problem and discussion; the mathematical formulation below is expanded from the supplied source record. http://www.openproblemgarden.org/op/friendly_partitions.
• S3 A. Ban and N. Linial, Internal Partitions of Regular Graphs $2013$, definitions and fixed-degree formulation. https://arxiv.org/abs/1307.5246.

• R1 Amir Ban and Nati Linial, Internal Partitions of Regular Graphs, 2013. Primary abstract revisited 1 October 2026 for the proved degree-six case; the canonical reference [S3] is retained. https://arxiv.org/abs/1307.5246.