Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Challenge 10: every ordinal clock for an infinite-minimum-degree core with finitely many outside hubs

Proved
TenChallenges.challenge_10_infiniteCore

by kmehltretter82 · Nov 14, 2026 · Mathlib 0df444a (Lean v4.33.1)

combinatoricsgraph-theoryinfinite-graphsten-challengesunfriendly-partition

Let G=(V,E)G=(V,E)G=(V,E) be a countable simple graph and let R⊆VR\subseteq VR⊆V be a subset of vertices such that:

  1. Every vertex x∈Rx\in Rx∈R has infinitely many neighbors inside RRR, i.e., ∣NG(x)∩R∣=∞|N_G(x)\cap R| = \infty∣NG​(x)∩R∣=∞.
  2. Only finitely many vertices outside RRR have infinite degree in GGG:
∣{x∈V∖R:deg⁡G(x)=∞}∣<∞.|\{x\in V\setminus R : \deg_G(x)=\infty\}| < \infty.∣{x∈V∖R:degG​(x)=∞}∣<∞.

Then Partitioner has a winning strategy in the unfriendly partitioning game on GGG starting from the empty partial coloring at every ordinal clock:

∀α∈Ord,PartitionerWins⁡(G,∅,α).\forall \alpha\in\mathrm{Ord},\quad \operatorname{PartitionerWins}(G,\varnothing,\alpha).∀α∈Ord,PartitionerWins(G,∅,α).

At each move, Challenger announces a vertex v∈Vv\in Vv∈V and a strictly smaller ordinal clock β<α\beta<\alphaβ<α, and Partitioner responds with a finite partial coloring extending the current position so that vvv has at least as many opposite-colored neighbors as same-colored neighbors.

This unifies and strictly generalizes two classical regimes of the Unfriendly Partition Problem: taking R=∅R=\varnothingR=∅ recovers the Aharoni-Milner-Prikry theorem for countable graphs with finitely many infinite-degree vertices, while taking R=VR=VR=V recovers countable graphs of infinite minimum degree, and intermediate choices allow an infinite-minimum-degree core attached arbitrarily to infinite locally-finite subgraphs and finitely many exceptional hubs.

Formalization Note. The core condition and outside-hub finiteness are expressed via (G.neighborSet x ∩ R).Infinite and {x : V | x ∉ R ∧ (G.neighborSet x).Infinite}.Finite. The vertex universe u and clock universe v are independent, using PartitionerWins and emptyPartition from Definitions.Def_TenChallenges_Challenge_10.

Preamble
import Definitions.Def_TenChallenges_Challenge_10
universe u v
Formal statement
namespace TenChallenges
theorem challenge_10_infiniteCore {V : Type u} [Countable V] (G : SimpleGraph V)
    (R : Set V) (hR : ∀ x ∈ R, (G.neighborSet x ∩ R).Infinite)
    (hOutside : {x : V | x ∉ R ∧ (G.neighborSet x).Infinite}.Finite)
    (r : Ordinal.{v}) : PartitionerWins G (emptyPartition V) r := by sorry
end TenChallenges
Source
Ten Challenges in Combinatorics, Challenge 10 (Unfriendly Partitioning Game), https://tenchallenges.github.io/ten-challenges/ ; generalizes R. Aharoni, E. C. Milner, and K. Prikry, Unfriendly partitions of a graph, J. Combin. Theory Ser. B 50 (1990), 1-10, Theorem 1, https://doi.org/10.1016/0095-8956(90)90092-E, and the finite-repair method in L. Aurichi and L. Real, Remarks on the countable case of the Unfriendly Partition Problem, Lemma 2.1, https://arxiv.org/abs/2412.14151.

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me