AFTD Auto-Formalizing Theoretical Domains

maxDegree_induce_V3_le_two_iff

theoremverified

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

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.

  1. 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.

    lines 6–8

    uses degree_le_maxDegree

      constructor
      · intro h v
        exact ((G.induce (simple_graph_V3 G : Set V)).degree_le_maxDegree v).trans h
  2. 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.

    lines 9–10

    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

/-- 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
See it in the graphDiscuss this resultChallenge it