All ordinal clocks with sparse incidence to infinite-degree vertices (Challenge 10)
ProvedTenChallenges.challenge_10_sparseHubIncidencecombinatoricsgraph-theoryinfinite-graphsten-challengesunfriendly-partition
Let 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 TenChallengesSource
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.