maxDegree_induce_V3_le_two_of_card_le_three
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.
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.
uses
maxDegree_induce_V3_le_two_iffrw [maxDegree_induce_V3_le_two_iff] intro v
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|$.
uses
degree_lt_card_verts,SetLike.coe_sort_coe,Fintype.card_coehave 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
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.
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.
- In Lean, the induced subgraph is formed on the coercion of the Finset `simple_graph_V3 G` to a `Set`, whose vertices form a subtype; lines 7–8 use `SetLike.coe_sort_coe` and `Fintype.card_coe` to identify the number of vertices of the induced subgraph with the Finset cardinality `(simple_graph_V3 G).card`, a distinction that does not exist on paper.
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.
/-- 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