AFTD Auto-Formalizing Theoretical Domains

petersen_graph_incidenceSet_ncard

theoremverified

The Petersen graph is cubic: every vertex x of petersen_graph lies in exactly 3 edges, (petersen_graph.incidenceSet x).ncard = 3.

Statement

theorem petersen_graph_incidenceSet_ncard (x : {s : Finset (Fin 5) // s.card = 2}) :
    (petersen_graph.incidenceSet x).ncard = 3
Source
Sanity check of petersen_graph (P10 is cubic), for arXiv:2610.35794 (Computational complexity of the H-coloring problem in cubic graphs)
Verified
30 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • petersen_graphThe Petersen graph P10, as the Kneser graph K(5,2): a SimpleGraph on the vertex type {s : Finset (Fin 5) // s.card = 2} of 2-element…

The proof, explained

The Petersen graph has vertices as 2-element subsets of a 5-element set, with edges connecting disjoint pairs. To prove that each vertex x is incident to exactly 3 edges, the proof first uses the canonical bijection between incident edges and neighbors to reduce the problem to counting neighbors of x. Since adjacency means being disjoint, the neighbors of x correspond bijectively to the 2-element subsets of the complement of x's underlying 2-set. Because the complement has 5 - 2 = 3 elements, the number of such subsets is (3 choose 2) = 3.

  1. The number of edges incident to x equals the number of neighbors of x.

    In any simple graph, the edges incident to a vertex x are canonically in bijection with the neighbors of x via SimpleGraph.incidenceSetEquivNeighborSet. By rewriting set cardinalities to subtype cardinals with Nat.card_coe_set_eq and applying Nat.card_congr across this bijection, we find that the incidence set and the neighbor set have the same cardinality, so it suffices to show that x has 3 neighbors.

    lines 3–8

    uses Nat.card_coe_set_eq, Nat.card_congr, SimpleGraph.incidenceSetEquivNeighborSet

      classical
      -- the incidence set of `x` is in bijection with its neighbour set
      have h1 : (petersen_graph.incidenceSet x).ncard = (petersen_graph.neighborSet x).ncard := by
        rw [← Nat.card_coe_set_eq, ← Nat.card_coe_set_eq]
        exact Nat.card_congr (SimpleGraph.incidenceSetEquivNeighborSet petersen_graph x)
      rw [h1]
  2. The set cardinality of the neighbor set equals the cardinality of the neighbor subtype as a finite type.

    Rewriting using Nat.card_coe_set_eq and Nat.card_eq_fintype_card converts the set cardinal `ncard` into `Fintype.card` of the subtype of neighbors of x.

    lines 9–11

    uses Nat.card_coe_set_eq, Nat.card_eq_fintype_card

      have h2 : (petersen_graph.neighborSet x).ncard = Fintype.card ↥(petersen_graph.neighborSet x) := by
        rw [← Nat.card_coe_set_eq, Nat.card_eq_fintype_card]
      rw [h2]
  3. Let s be the 2-element subset of Fin 5 representing vertex x.

    Vertices of the Petersen graph are defined as pairs consisting of a subset s ⊆ Fin 5 together with a proof that its cardinality is 2. We name this subset s and note that s.card = 2.

    lines 12–13

      set s : Finset (Fin 5) := x.1
      have hscard : s.card = 2 := x.2
  4. The neighbors of x are in bijection with the 2-element subsets of the complement sᶜ.

    In the Petersen graph, two vertices are adjacent if and only if their underlying 2-element subsets are disjoint. A subset is disjoint from s if and only if it is contained in the complement sᶜ (by Finset.disjoint_left and Finset.mem_compl). Thus, sending a neighbor to its underlying set yields a 2-element subset of sᶜ (using Finset.mem_powersetCard and Finset.disjoint_left.mp), and conversely, any 2-element subset of sᶜ is disjoint from s and yields a neighbor of x (using Finset.mem_powersetCard.mp). These assignments are mutually inverse, defining an equivalence e.

    lines 15–30

    uses Finset.mem_powersetCard, Finset.mem_compl, Finset.disjoint_left.mp, Finset.mem_powersetCard.mp, Finset.disjoint_left

      have e : ↥(petersen_graph.neighborSet x) ≃ ↥((sᶜ).powersetCard 2) :=
      { toFun := fun t : ↥(petersen_graph.neighborSet x) => (⟨t.1.1, by
          rw [Finset.mem_powersetCard]
          refine ⟨fun a ha => ?_, t.1.2⟩
          rw [Finset.mem_compl]
          intro hsa
          exact Finset.disjoint_left.mp t.2 hsa ha⟩ : ↥((sᶜ).powersetCard 2))
        invFun := fun u : ↥((sᶜ).powersetCard 2) => (⟨⟨u.1, (Finset.mem_powersetCard.mp u.2).2⟩, by
          change Disjoint (s : Finset (Fin 5)) (u.1 : Finset (Fin 5))
          rw [Finset.disjoint_left]
          intro a hsa hau
          have h : a ∈ sᶜ := (Finset.mem_powersetCard.mp u.2).1 hau
          rw [Finset.mem_compl] at h
          exact h hsa⟩ : ↥(petersen_graph.neighborSet x))
        left_inv := fun t => rfl
        right_inv := fun u => rfl }
  5. The number of neighbors is (5 - 2).choose 2 = 3, completing the proof.

    Rewriting by Fintype.card_congr with the bijection e replaces the neighbor count by the cardinality of (sᶜ).powersetCard 2. By Finset.card_coe, Finset.card_powersetCard, Finset.card_compl, and s.card = 2, this is ((Fintype.card (Fin 5) - 2).choose 2), which norm_num evaluates to 3.

    lines 31–32

    uses Fintype.card_congr, Fintype.card_coe, Finset.card_powersetCard, Finset.card_compl

      rw [Fintype.card_congr e, Fintype.card_coe, Finset.card_powersetCard, Finset.card_compl, hscard]
      norm_num
Nat.card_coe_set_eq
The cardinal `Nat.card` of a set coerced to a subtype equals its set cardinality `ncard`.
Nat.card_congr
If two types are equivalent via a bijection, their cardinals (`Nat.card`) are equal.
SimpleGraph.incidenceSetEquivNeighborSet
In any simple graph, the set of edges incident to a vertex is canonically in bijection with the vertex's set of neighbors.
Nat.card_eq_fintype_card
For any finite type, its cardinal `Nat.card` equals its `Fintype.card`.
Finset.mem_powersetCard
A finite set belongs to `Finset.powersetCard n t` if and only if it is a subset of `t` with cardinality `n`.
Finset.mem_compl
An element belongs to the complement of a finite set if and only if it does not belong to the set.
Finset.disjoint_left.mp
If two finite sets are disjoint, any element belonging to the first does not belong to the second.
Finset.mem_powersetCard.mp
If a finite set belongs to `Finset.powersetCard n t`, it is a subset of `t` and has cardinality `n`.
Finset.disjoint_left
Two finite sets are disjoint if and only if no element of the first belongs to the second.
Fintype.card_congr
If two finite types are equivalent via a bijection, their `Fintype.card` values are equal.
Fintype.card_coe
The cardinality of a finite set coerced to a subtype equals the cardinality of the finite set.
Finset.card_powersetCard
The number of `n`-element subsets of a finite set `s` is `s.card.choose n`.
Finset.card_compl
The cardinality of the complement of a subset `s` in a finite universe `α` is `Fintype.card α - s.card`.

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

theorem petersen_graph_incidenceSet_ncard (x : {s : Finset (Fin 5) // s.card = 2}) :    (petersen_graph.incidenceSet x).ncard = 3 := by  classical  -- the incidence set of `x` is in bijection with its neighbour set  have h1 : (petersen_graph.incidenceSet x).ncard = (petersen_graph.neighborSet x).ncard := by    rw [← Nat.card_coe_set_eq, ← Nat.card_coe_set_eq]    exact Nat.card_congr (SimpleGraph.incidenceSetEquivNeighborSet petersen_graph x)  rw [h1]  have h2 : (petersen_graph.neighborSet x).ncard = Fintype.card ↥(petersen_graph.neighborSet x) := by    rw [← Nat.card_coe_set_eq, Nat.card_eq_fintype_card]  rw [h2]  set s : Finset (Fin 5) := x.1  have hscard : s.card = 2 := x.2  -- a vertex `t` is a neighbour of `x` iff `t.1 ⊆ sᶜ`, i.e. `t.1 ∈ (sᶜ).powersetCard 2`  have e : ↥(petersen_graph.neighborSet x) ≃ ↥((sᶜ).powersetCard 2) :=  { toFun := fun t : ↥(petersen_graph.neighborSet x) => (⟨t.1.1, by      rw [Finset.mem_powersetCard]      refine ⟨fun a ha => ?_, t.1.2⟩      rw [Finset.mem_compl]      intro hsa      exact Finset.disjoint_left.mp t.2 hsa ha⟩ : ↥((sᶜ).powersetCard 2))    invFun := fun u : ↥((sᶜ).powersetCard 2) => (⟨⟨u.1, (Finset.mem_powersetCard.mp u.2).2⟩, by      change Disjoint (s : Finset (Fin 5)) (u.1 : Finset (Fin 5))      rw [Finset.disjoint_left]      intro a hsa hau      have h : a ∈ sᶜ := (Finset.mem_powersetCard.mp u.2).1 hau      rw [Finset.mem_compl] at h      exact h hsa⟩ : ↥(petersen_graph.neighborSet x))    left_inv := fun t => rfl    right_inv := fun u => rfl }  rw [Fintype.card_congr e, Fintype.card_coe, Finset.card_powersetCard, Finset.card_compl, hscard]  norm_num
See it in the graphDiscuss this resultChallenge it