Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

All ordinal clocks with sparse incidence to infinite-degree vertices (Challenge 10)

Proved
TenChallenges.challenge_10_sparseHubIncidence

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

combinatoricsgraph-theoryinfinite-graphsten-challengesunfriendly-partition

Let GGG be a countable simple graph. Suppose each finite-degree vertex has at most one infinite-degree neighbour, or has even degree and at most two infinite-degree neighbours. Then Partitioner wins the Challenge 10 game from the empty partial partition for every ordinal clock. Edges between infinite-degree vertices are unrestricted.

Preamble
import Definitions.Def_TenChallenges_Challenge_10
import Mathlib.Data.Set.Card
universe u v
Formal statement
namespace TenChallenges
theorem challenge_10_sparseHubIncidence {V : Type u} [Countable V] (G : SimpleGraph V)
    (hthin : ∀ x, (G.neighborSet x).Finite →
      (G.neighborSet x ∩ {y | (G.neighborSet y).Infinite}).ncard ≤ 1 ∨
        (G.neighborSet x ∩ {y | (G.neighborSet y).Infinite}).ncard ≤ 2 ∧
          Even (G.neighborSet x).ncard) :
    ∀ r : Ordinal.{v}, PartitionerWins G (emptyPartition V) r := by sorry
end TenChallenges
Source
Ten Challenges in Combinatorics, Challenge 10 (https://tenchallenges.github.io/ten-challenges/). This theorem proves the all-clock conclusion for graphs satisfying the stated incidence condition.

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