AFTD Auto-Formalizing Theoretical Domains

simple_graph_vertex_dominated_complete_two

theoremverified

In the complete graph on two vertices, vertex 0 is dominated.

Statement

theorem simple_graph_vertex_dominated_complete_two :
    simple_graph_vertex_dominated (⊤ : SimpleGraph (Fin 2)) (0 : Fin 2)
Source
arXiv:2611.14430 Section 2
Verified
12 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • simple_graph_vertex_dominatedA vertex $v$ of a simple graph $H$ is dominated if there exists a vertex $t \neq v$ in $H$ such that the closed neighbourhood of $v$ is…

Read back from the Lean

In the complete simple graph on the vertex set Fin 2, the vertex 0 is dominated; that is, there exists a vertex t : Fin 2 such that t ≠ 0 and the closed neighborhood of 0 (the set formed by inserting 0 into the neighbor set of 0) is a subset of the closed neighborhood of t (the set formed by inserting t into the neighbor set of t).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

To show that vertex 0 is dominated in the complete graph on two vertices, we exhibit vertex 1 as the dominating vertex. Vertex 1 is distinct from vertex 0, and in a complete graph on two vertices, the closed neighborhood of vertex 1 contains all vertices of the graph, so it trivially contains the closed neighborhood of vertex 0. The proof verifies this by checking each of the two vertices 0 and 1.

  1. Vertex 1 is chosen as the dominating vertex, reducing the goal to showing that the closed neighborhood of vertex 0 is contained in the closed neighborhood of vertex 1.

    We provide vertex 1 as the witness for the existential quantifier in the definition of domination (`use 1`). We must then show that 1 ≠ 0 and that the closed neighborhood of 0 is a subset of the closed neighborhood of 1. The inequality 1 ≠ 0 is proved by finite evaluation (`decide`), leaving only the subset inclusion.

    lines 4–5

      use 1
      refine ⟨by decide, ?_⟩
  2. To prove the inclusion, it suffices to check the two possible vertices, 0 and 1.

    We take an arbitrary vertex x assumed to lie in the closed neighborhood of 0 (`intro x _`). Because the vertex type is Fin 2, we exhaustively split into two cases: x = 0 and x = 1 (`fin_cases x`).

    lines 6–7

      intro x _
      fin_cases x
  3. Vertex 0 belongs to the closed neighborhood of vertex 1.

    In the case x = 0, we must show 0 ∈ {1} ∪ N(1). Choosing the right alternative (`right`) leaves the goal of showing that 0 is adjacent to 1 in the complete graph (0 ∈ N(1)). In the complete graph ⊤, distinct vertices are connected by an edge; simplifying this condition reduces to 0 ≠ 1 and closes the goal (`simp`).

    lines 8–9

      · right
        simp
  4. Vertex 1 belongs to the closed neighborhood of vertex 1.

    In the case x = 1, we must show 1 ∈ {1} ∪ N(1). Choosing the left alternative (`left`) leaves the equality 1 = 1, which holds by reflexivity (`rfl`).

    lines 10–11

      · left
        rfl

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

/-- In the complete graph on two vertices, vertex 0 is dominated by vertex 1. -/theorem simple_graph_vertex_dominated_complete_two :    simple_graph_vertex_dominated (⊤ : SimpleGraph (Fin 2)) (0 : Fin 2) := by  use 1  refine ⟨by decide, ?_⟩  intro x _  fin_cases x  · right    simp  · left    rfl
See it in the graphDiscuss this resultChallenge it