maxDegree_induce_V3_le_two_iff
For any finite simple graph G with decidable adjacency on a finite type V with decidable equality, the induced subgraph on the set of degree-3 vertices has maximum degree at most 2 if and only if every vertex in that set has degree at most 2 in the induced subgraph.
Statement
theorem maxDegree_induce_V3_le_two_iff {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] : (G.induce (simple_graph_V3 G : Set V)).maxDegree ≤ 2 ↔ ∀ v : (simple_graph_V3 G : Set V), (G.induce (simple_graph_V3 G : Set V)).degree v ≤ 2
- Source
- arXiv:2610.21868 Sec. 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…
- Used by 2
- maxDegree_induce_V3_le_two_iff_neighbor_filterFor any finite simple graph G, the induced subgraph on the vertices of degree 3 has maximum degree at most 2 if and only if every degree-3…
- maxDegree_induce_V3_le_two_of_card_le_threeFor 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…
Read back from the Lean
For any finite type $V$ with decidable equality and any simple graph $G$ on $V$ with decidable adjacency, the maximum degree of the subgraph of $G$ induced on the set of vertices of degree 3 is at most 2 if and only if every vertex in that induced subgraph has degree at most 2 in the induced subgraph.
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 equivalence is proved by splitting into two directions. In the forward direction, the degree of every vertex in the induced subgraph is bounded above by the maximum degree, which is at most 2 by assumption. In the reverse direction, since every vertex has degree at most 2, the maximum degree is at most 2 by the universal bound characterizing the maximum degree.
In the induced subgraph G[V₃], if the maximum degree is at most 2, then every vertex has degree at most 2.
We split the bi-implication and consider the forward direction. Assuming the maximum degree of G[V₃] is at most 2, the degree of any vertex v ∈ V₃ in G[V₃] is bounded above by the maximum degree of G[V₃] via `degree_le_maxDegree`. By transitivity with the hypothesis, the degree of v is at most 2.
uses
degree_le_maxDegreeconstructor · intro h v exact ((G.induce (simple_graph_V3 G : Set V)).degree_le_maxDegree v).trans h
In the induced subgraph G[V₃], if every vertex has degree at most 2, then the maximum degree is at most 2.
For the reverse direction, we assume that every vertex v ∈ V₃ has degree at most 2 in G[V₃]. By `maxDegree_le_of_forall_degree_le`, if all vertex degrees in a graph are bounded by k, then its maximum degree is at most k. Applying this lemma with k = 2 completes the equivalence.
uses
maxDegree_le_of_forall_degree_le· intro h exact (G.induce (simple_graph_V3 G : Set V)).maxDegree_le_of_forall_degree_le 2 h
degree_le_maxDegree- In any finite graph, the degree of every vertex is at most the maximum degree of the graph.
maxDegree_le_of_forall_degree_le- If every vertex in a finite graph has degree at most k, then the maximum degree of the graph is at most k.
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.
/-- Equivalence between maxDegree of G[V_3] <= 2 and every vertex in V_3 having degree <= 2. -/theorem maxDegree_induce_V3_le_two_iff {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] : (G.induce (simple_graph_V3 G : Set V)).maxDegree ≤ 2 ↔ ∀ v : (simple_graph_V3 G : Set V), (G.induce (simple_graph_V3 G : Set V)).degree v ≤ 2 := by constructor · intro h v exact ((G.induce (simple_graph_V3 G : Set V)).degree_le_maxDegree v).trans h · intro h exact (G.induce (simple_graph_V3 G : Set V)).maxDegree_le_of_forall_degree_le 2 h