AFTD Auto-Formalizing Theoretical Domains

complete_four_not_induce_V3_maxDegree_le_two

theoremverifiedformalization

In the complete simple graph on vertices Fin 4, the induced subgraph on the set of degree-3 vertices does not have maximum degree at most 2.

Statement

theorem complete_four_not_induce_V3_maxDegree_le_two :
    ¬ ((⊤ : SimpleGraph (Fin 4)).induce (simple_graph_V3 (⊤ : SimpleGraph (Fin 4)) : Set (Fin 4))).maxDegree ≤ 2
Formalizes
arXiv:2610.21868, Section 4
Verified
25 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • simple_graph_V3For a finite type V with decidable equality and a simple graph G on V with decidable adjacency, simple_graph_V3 G is the finset of all…

Read back from the Lean

In the complete graph on 4 vertices (the complete graph on Fin 4), let $S$ be the set of vertices with degree 3. The theorem asserts that it is not the case that the maximum degree of the subgraph induced by $S$ is less than or equal to 2 (i.e., the maximum degree of this induced subgraph is strictly greater than 2).

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

In the complete graph on four vertices $K_4$, every vertex is adjacent to all other three vertices and therefore has degree 3. Consequently, the induced subgraph on the degree-3 vertices is $K_4$ itself, which has maximum degree 3. Because this is a finite graph, Lean's `decide` tactic establishes the strict inequality $3 > 2$ by direct finite evaluation.

  1. The maximum degree of the subgraph of $K_4$ induced by its degree-3 vertices is not at most 2. automation

    In the complete graph on four vertices $K_4$, every vertex is adjacent to all three other vertices, so each vertex has degree 3. Thus, the set of degree-3 vertices comprises the entire vertex set, and the induced subgraph is $K_4$ itself. The maximum degree of this subgraph is 3, which is strictly greater than 2. Because the vertex type $\text{Fin } 4$ is finite and all relations are decidable, the `decide` tactic confirms this inequality by direct computation.

    line 4

      decide

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 four vertices, the induced subgraph on the degree-3 vertices does not have maximum degree at most 2. -/theorem complete_four_not_induce_V3_maxDegree_le_two :    ¬ ((⊤ : SimpleGraph (Fin 4)).induce (simple_graph_V3 (⊤ : SimpleGraph (Fin 4)) : Set (Fin 4))).maxDegree ≤ 2 := by  decide
See it in the graphDiscuss this resultChallenge it