AFTD Auto-Formalizing Theoretical Domains

maxDegree_induce_V3_le_two_of_card_le_three

theoremverified

For any finite simple graph G, if the number of vertices of degree 3 in G is at most 3, then the induced subgraph on the set of degree-3 vertices has maximum degree at most 2.

Statement

theorem maxDegree_induce_V3_le_two_of_card_le_three {V : Type*} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) [DecidableRel G.Adj] (hcard : (simple_graph_V3 G).card ≤ 3) :
    (G.induce (simple_graph_V3 G : Set V)).maxDegree ≤ 2
Source
folklore
Verified
25 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • 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…
  • maxDegree_induce_V3_le_two_iffFor any finite simple graph G with decidable adjacency on a finite type V with decidable equality, the induced subgraph on the set of…
Used by 1
  • op_310_partial_maxDegree_le_twoEvery finite simple graph with maximum degree at most 2 satisfies the Delta(G[V_3]) <= 2 condition and admits a rich-neighbor…

Read back from the Lean

For any finite type $V$ with decidable equality and any simple graph $G$ on $V$ with decidable adjacency: if the number of vertices of degree 3 in $G$ is at most 3, then the maximum degree of the subgraph of $G$ induced by the vertices of degree 3 is at most 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

The argument reduces the bound on the maximum degree of the induced subgraph $G[V_3]$ to bounding the degree of each of its vertices by 2. In any finite simple graph, the degree of a vertex is strictly less than the total number of vertices in the graph. Because $|V_3| \le 3$, the degree of any vertex in $G[V_3]$ is strictly less than 3, and therefore at most 2.

  1. It suffices to show that every vertex in the induced subgraph on $V_3$ has degree at most 2.

    By `maxDegree_induce_V3_le_two_iff`, the maximum degree of the induced subgraph $G[V_3]$ is at most 2 if and only if each of its vertices has degree at most 2. We then introduce an arbitrary vertex $v$ of this induced subgraph.

    lines 5–6

    uses maxDegree_induce_V3_le_two_iff

      rw [maxDegree_induce_V3_le_two_iff]
      intro v
  2. The degree of $v$ in the induced subgraph $G[V_3]$ is strictly less than $|V_3|$.

    In any simple graph, no vertex can be adjacent to itself, so its degree is strictly less than the total number of vertices (`degree_lt_card_verts`). Applying this to the induced subgraph $G[V_3]$ and simplifying the vertex type's cardinality to the finset cardinality $|V_3|$ via `SetLike.coe_sort_coe` and `Fintype.card_coe` gives $\deg_{G[V_3]}(v) < |V_3|$.

    lines 7–8

    uses degree_lt_card_verts, SetLike.coe_sort_coe, Fintype.card_coe

      have h1 := (G.induce (simple_graph_V3 G : Set V)).degree_lt_card_verts v
      simp only [SetLike.coe_sort_coe, Fintype.card_coe] at h1
  3. The degree of $v$ in $G[V_3]$ is at most 2. automation

    Since $\deg_{G[V_3]}(v) < |V_3|$ and by hypothesis $|V_3| \le 3$, linear arithmetic on natural numbers (`omega`) finishes the proof.

    line 9

      omega
maxDegree_induce_V3_le_two_iff
The maximum degree of the induced subgraph on the set of degree-3 vertices is at most 2 if and only if every vertex in that induced subgraph has degree at most 2.
degree_lt_card_verts
In any finite simple graph, the degree of any vertex is strictly less than the total number of vertices in the graph.
SetLike.coe_sort_coe
Coercing a set-like structure to a set and then to a type sort is definitionally equal to coercing it directly to a type sort.
Fintype.card_coe
The cardinality of a finite set coerced to a subtype is equal to the cardinality of the original finset.

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

/-- If a finite simple graph has at most three vertices of degree 3, then the induced subgraph on its degree-3 vertices has maximum degree at most 2. -/theorem maxDegree_induce_V3_le_two_of_card_le_three {V : Type*} [Fintype V] [DecidableEq V]    (G : SimpleGraph V) [DecidableRel G.Adj] (hcard : (simple_graph_V3 G).card ≤ 3) :    (G.induce (simple_graph_V3 G : Set V)).maxDegree ≤ 2 := by  rw [maxDegree_induce_V3_le_two_iff]  intro v  have h1 := (G.induce (simple_graph_V3 G : Set V)).degree_lt_card_verts v  simp only [SetLike.coe_sort_coe, Fintype.card_coe] at h1  omega
See it in the graphDiscuss this resultChallenge it