complete_four_not_induce_V3_maxDegree_le_two
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.
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.
decide
- The entire proof is carried out by Lean's computational kernel via `decide`: because the graph has only four vertices, the degrees, the induced subgraph, and its maximum degree are computed directly by finite reflection.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- 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