AFTD Auto-Formalizing Theoretical Domains

subcubic_isAcyclic_exists_leaf_edge_dist_two_le_four

theoremverified

In any finite forest of maximum degree at most 3 with at least one edge, there exists a leaf edge e (one endpoint having degree 1) with at most 4 edges at distance ≤ 2 in the line graph.

Statement

theorem subcubic_isAcyclic_exists_leaf_edge_dist_two_le_four {V : Type*}
    [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj]
    (hdeg : G.maxDegree ≤ 3) (hforest : G.IsAcyclic)
    (hne : G.edgeFinset.Nonempty) :
    ∃ (e : G.edgeSet) (v : V), v ∈ e.val ∧ G.degree v = 1 ∧
      ((Finset.univ.erase e).filter (fun f : G.edgeSet =>
        G.lineGraph.Adj e f ∨ ∃ g : G.edgeSet, G.lineGraph.Adj g e ∧ G.lineGraph.Adj g f)).card ≤ 4
Source
step towards subcubic_isAcyclic_exists_rich_neighbor_five_coloring
Verified
23 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
Used by 2

The proof, explained

We choose a simple path p of maximal length in the forest G, starting at v₀ with second vertex u = p.snd. By maximality and the acyclicity of G, the endpoint v₀ has degree 1, making e₀ = {v₀, u} a leaf edge, and any other neighbor of u off the path must also have degree 1. Because u can have at most one neighbor on the rest of p and the maximum degree of G is at most 3, the set U = N(u) \ {v₀} has size at most 2 and contains at most one vertex of degree ≥ 2, giving ∑_{w ∈ U} deg(w) ≤ 4. Finally, every edge at distance 1 or 2 from e₀ in the line graph must be incident to some vertex in U, so the number of such edges is bounded by ∑_{w ∈ U} deg(w) ≤ 4.

  1. Set up the classical reasoning environment.

    Two auxiliary hypotheses about colorings are declared and immediately discarded, and classical logic is opened for the remainder of the proof.

    lines 9–13

    uses maxDegree_le_two_exists_rich_neighbor_five_coloring_decRelLineGraphAdj, maxDegree_le_two_exists_rich_neighbor_five_coloring

      have _hinst := @maxDegree_le_two_exists_rich_neighbor_five_coloring_decRelLineGraphAdj V
      clear _hinst
      have _howner := @maxDegree_le_two_exists_rich_neighbor_five_coloring V
      clear _howner
      classical
  2. The vertex set V is nonempty.

    The graph contains at least one edge e = {a, b}, so taking one of its endpoints shows V has at least one element.

    lines 14–17

    uses SimpleGraph.mem_edgeFinset, Sym2.inductionOn, SimpleGraph.not_isDiag_of_mem_edgeSet

      have hV : Nonempty V := by
        obtain ⟨e, he⟩ := hne
        rw [SimpleGraph.mem_edgeFinset] at he
        exact Sym2.inductionOn e (fun a b _ => ⟨a⟩) (SimpleGraph.not_isDiag_of_mem_edgeSet (G := G) he)
  3. There exists a simple path p in G of maximal length.

    Since the vertex set is nonempty and the edge set is finite, there exists a simple path p from some vertex v₀ to vk whose length is maximal among all simple paths in G.

    lines 18–19

    uses SimpleGraph.Walk.exists_isPath_forall_isPath_length_le_length, Finite.of_fintype

      obtain ⟨v0, vk, p, hp, hmax⟩ :=
        @SimpleGraph.Walk.exists_isPath_forall_isPath_length_le_length V G hV (Finite.of_fintype G.edgeSet)
  4. The path p has length at least 1 and is therefore not nil.

    Any edge in G forms a simple path of length 1, so the maximum path length is at least 1. Consequently, p cannot be the empty walk Nil.

    lines 20–30

    uses SimpleGraph.mem_edgeFinset, Sym2.inductionOn, SimpleGraph.mem_edgeSet, SimpleGraph.Walk.IsPath.of_adj, SimpleGraph.Walk.length_eq_zero_iff

      have hK1 : 1 ≤ p.length := by
        obtain ⟨e, he⟩ := hne
        rw [SimpleGraph.mem_edgeFinset] at he
        refine Sym2.inductionOn e (f := fun e => e ∈ G.edgeSet → 1 ≤ p.length) ?_ he
        intro a b hmem
        have hab : G.Adj a b := (SimpleGraph.mem_edgeSet G).mp hmem
        have hpth : hab.toWalk.IsPath := SimpleGraph.Walk.IsPath.of_adj hab
        have h := hmax a b hab.toWalk hpth
        simpa using h
      have hnil : ¬ p.Nil := by
        rw [← SimpleGraph.Walk.length_eq_zero_iff]; omega
  5. Decompose p into v₀, its neighbor p.snd, and the tail path p.tail.

    Because p is not nil, it splits into an initial edge from v₀ to p.snd followed by p.tail, which is also a simple path. Its vertices are v₀ followed by the vertices of p.tail, so any vertex on p distinct from v₀ belongs to the tail.

    lines 31–41

    uses SimpleGraph.Walk.cons_tail_eq, SimpleGraph.Walk.support_cons, List.mem_cons

      have hp_tail : p.tail.IsPath := hp.tail
      have hadj : G.Adj v0 p.snd := p.adj_snd hnil
      have hdecomp : p.support = v0 :: p.tail.support := by
        conv_lhs => rw [← SimpleGraph.Walk.cons_tail_eq p hnil]
        rw [SimpleGraph.Walk.support_cons]
      have hsupp_tail_of : ∀ {w : V}, w ∈ p.support → w ≠ v0 → w ∈ p.tail.support := by
        intro w hw hwv0
        rw [hdecomp] at hw
        rcases List.mem_cons.mp hw with h | h
        · exact absurd h hwv0
        · exact h
  6. The starting vertex of any maximum-length path is a leaf, so deg(v₀) = 1.

    Let r be any path of the same length as p starting at a. The second vertex of r is adjacent to a. If a had any other neighbor w, then w cannot lie on r because G is acyclic (a forest cannot contain a chord or cycle). But if w does not lie on r, prepending w creates a strictly longer simple path, contradicting maximality. Hence a has degree 1, and in particular deg(v₀) = 1.

    lines 42–54

    uses SimpleGraph.Walk.length_eq_zero_iff, SimpleGraph.degree_eq_one_iff_existsUnique_adj, SimpleGraph.Walk.length_cons

      have start_leaf : ∀ {a b : V} (r : G.Walk a b), r.IsPath → r.length = p.length → G.degree a = 1 := by
        intro a b r hr hrlen
        have hrnil : ¬ r.Nil := by rw [← SimpleGraph.Walk.length_eq_zero_iff]; omega
        rw [SimpleGraph.degree_eq_one_iff_existsUnique_adj]
        refine ⟨r.snd, r.adj_snd hrnil, fun w hw => ?_⟩
        by_cases hmem : w ∈ r.support
        · exact hforest.eq_snd_of_adj_start hr hw hmem
        · exfalso
          have hp' : (r.cons hw.symm).IsPath := hr.cons hmem
          have hlt := hmax w b (r.cons hw.symm) hp'
          rw [SimpleGraph.Walk.length_cons, hrlen] at hlt
          omega
      have deg_v0 : G.degree v0 = 1 := start_leaf p hp rfl
  7. Neighbors of p.snd outside p have degree 1, and any neighbor of p.snd on p.tail is its immediate successor.

    If w is a neighbor of p.snd not on p, replacing the initial edge {v₀, p.snd} with {w, p.snd} yields a new path of maximum length starting at w, so deg(w) = 1. Furthermore, by acyclicity, p.snd cannot have any neighbor on p.tail other than the very next vertex of the path.

    lines 55–64

    uses List.mem_cons_of_mem, SimpleGraph.Walk.length_cons, SimpleGraph.Walk.length_tail

      have leaf_offpath : ∀ w : V, G.Adj p.snd w → w ∉ p.support → G.degree w = 1 := by
        intro w hwu hwsupp
        have hwt : w ∉ p.tail.support := fun h => hwsupp (by rw [hdecomp]; exact List.mem_cons_of_mem _ h)
        have hpth : (p.tail.cons hwu.symm).IsPath := hp_tail.cons hwt
        have hlen : (p.tail.cons hwu.symm).length = p.length := by
          rw [SimpleGraph.Walk.length_cons, SimpleGraph.Walk.length_tail]; omega
        exact start_leaf (p.tail.cons hwu.symm) hpth hlen
      have onpath_eq : ∀ w : V, G.Adj p.snd w → w ∈ p.tail.support → w = p.tail.snd := by
        intro w hwu hwt
        exact hforest.eq_snd_of_adj_start hp_tail hwu hwt
  8. Among the neighbors of p.snd other than v₀, at most one vertex has degree at least 2.

    Let U = N(p.snd) \ {v₀}. If w₁ and w₂ are two distinct vertices in U, they cannot both lie on p.tail since p.snd has at most one neighbor on p.tail. Thus at least one of them lies off p, implying its degree is 1. Therefore, at most one vertex in U has degree ≥ 2.

    lines 65–76

    uses Finset.mem_erase, SimpleGraph.mem_neighborFinset

      have hmemU : ∀ w, w ∈ (G.neighborFinset p.snd).erase v0 ↔ w ≠ v0 ∧ G.Adj p.snd w := by
        intro w; rw [Finset.mem_erase, SimpleGraph.mem_neighborFinset]
      have pairwise : ∀ w1 ∈ (G.neighborFinset p.snd).erase v0, ∀ w2 ∈ (G.neighborFinset p.snd).erase v0,
          w1 ≠ w2 → G.degree w1 = 1 ∨ G.degree w2 = 1 := by
        intro w1 h1 w2 h2 hne12
        obtain ⟨h1v, hadj1⟩ := (hmemU w1).mp h1
        obtain ⟨h2v, hadj2⟩ := (hmemU w2).mp h2
        by_cases hsup1 : w1 ∈ p.tail.support
        · by_cases hsup2 : w2 ∈ p.tail.support
          · exact absurd (by rw [onpath_eq w1 hadj1 hsup1, onpath_eq w2 hadj2 hsup2]) hne12
          · right; exact leaf_offpath w2 hadj2 (fun h => hsup2 (hsupp_tail_of h h2v))
        · left; exact leaf_offpath w1 hadj1 (fun h => hsup1 (hsupp_tail_of h h1v))
  9. The edge e₀ = {v₀, p.snd} is the unique edge incident to v₀, and any other edge sharing a vertex with e₀ must contain p.snd.

    Since deg(v₀) = 1, e₀ is the only edge at v₀. Any other edge g ≠ e₀ that intersects e₀ cannot contain v₀, so it must contain p.snd.

    lines 77–98

    uses SimpleGraph.mem_edgeSet, Finset.card_eq_one, SimpleGraph.mem_incidenceFinset, Sym2.mem_mk_left, Finset.mem_singleton, Subtype.ext, Sym2.mem_iff

      let e0 : G.edgeSet := ⟨s(v0, p.snd), (SimpleGraph.mem_edgeSet G).mpr hadj⟩
      have he0v : (e0 : Sym2 V) = s(v0, p.snd) := rfl
      have hinc_v0 : ∀ f : G.edgeSet, v0 ∈ (f : Sym2 V) → f = e0 := by
        intro f hf
        have hcard : (G.incidenceFinset v0).card = 1 := by
          rw [G.card_incidenceFinset_eq_degree]; exact deg_v0
        obtain ⟨x, hx⟩ := Finset.card_eq_one.mp hcard
        have hxe : (e0 : Sym2 V) ∈ G.incidenceFinset v0 := by
          rw [SimpleGraph.mem_incidenceFinset]; exact ⟨e0.2, by rw [he0v]; exact Sym2.mem_mk_left _ _⟩
        rw [hx] at hxe
        simp only [Finset.mem_singleton] at hxe
        have hfmem : (f : Sym2 V) ∈ G.incidenceFinset v0 := by
          rw [SimpleGraph.mem_incidenceFinset]; exact ⟨f.2, hf⟩
        rw [hx] at hfmem
        simp only [Finset.mem_singleton] at hfmem
        exact Subtype.ext (hfmem.trans hxe.symm)
      have share_e0 : ∀ g : G.edgeSet, (∃ x, x ∈ (e0 : Sym2 V) ∧ x ∈ (g : Sym2 V)) → g ≠ e0 → p.snd ∈ (g : Sym2 V) := by
        intro g ⟨x, hxe0, hxg⟩ hge
        have hx : x = v0 ∨ x = p.snd := by rw [he0v] at hxe0; exact Sym2.mem_iff.mp hxe0
        rcases hx with rfl | rfl
        · exact absurd (hinc_v0 g hxg) hge
        · exact hxg
  10. Every edge f ≠ e₀ at distance 1 or 2 from e₀ in the line graph has an endpoint in U = N(p.snd) \ {v₀}.

    If f is adjacent to e₀ in the line graph, they share a vertex, which must be p.snd; the other endpoint of f is in U. If f is at distance 2, there is an intermediate edge g adjacent to both e₀ and f. Then g contains p.snd, so g = {p.snd, u} with u ∈ U. The edge f shares an endpoint with g, which is either p.snd (so f connects to U) or u ∈ U directly. In either case, f has an endpoint in U.

    lines 99–135

    uses Sym2.Mem.other, Sym2.other_mem, Sym2.other_spec, SimpleGraph.mem_edgeSet, Subtype.ext, Sym2.eq_swap, SimpleGraph.lineGraph_adj_iff_exists, Sym2.mem_iff

      have incidence_step : ∀ f : G.edgeSet, p.snd ∈ (f : Sym2 V) → f ≠ e0 →
          ∃ w ∈ (G.neighborFinset p.snd).erase v0, w ∈ (f : Sym2 V) := by
        intro f hps hfe
        refine ⟨Sym2.Mem.other hps, ?_, Sym2.other_mem hps⟩
        have hadj' : G.Adj p.snd (Sym2.Mem.other hps) := by
          have hmem : s(p.snd, Sym2.Mem.other hps) ∈ G.edgeSet := by
            rw [Sym2.other_spec hps]; exact f.2
          exact (SimpleGraph.mem_edgeSet G).mp hmem
        have hne : Sym2.Mem.other hps ≠ v0 := by
          intro h
          apply hfe; apply Subtype.ext
          rw [← Sym2.other_spec hps, h, he0v]; exact Sym2.eq_swap
        exact (hmemU _).mpr ⟨hne, hadj'⟩
      have cover : ∀ f : G.edgeSet, f ≠ e0 →
          (G.lineGraph.Adj e0 f ∨ ∃ g : G.edgeSet, G.lineGraph.Adj g e0 ∧ G.lineGraph.Adj g f) →
          ∃ w ∈ (G.neighborFinset p.snd).erase v0, w ∈ (f : Sym2 V) := by
        intro f hfe hdist
        rcases hdist with h1 | ⟨g, hg1, hg2⟩
        · obtain ⟨_, x, hx0, hxf⟩ := (SimpleGraph.lineGraph_adj_iff_exists).mp h1
          exact incidence_step f (share_e0 f ⟨x, hx0, hxf⟩ hfe) hfe
        · obtain ⟨hge, x, hx0, hxg⟩ := (SimpleGraph.lineGraph_adj_iff_exists).mp hg1
          obtain ⟨_, y, hyg, hyf⟩ := (SimpleGraph.lineGraph_adj_iff_exists).mp hg2
          have hpsg : p.snd ∈ (g : Sym2 V) := share_e0 g ⟨x, hxg, hx0⟩ hge
          have hspec : s(p.snd, Sym2.Mem.other hpsg) = (g : Sym2 V) := Sym2.other_spec hpsg
          have hy : y = p.snd ∨ y = Sym2.Mem.other hpsg := by
            rw [← hspec] at hyg; exact Sym2.mem_iff.mp hyg
          rcases hy with rfl | rfl
          · exact incidence_step f hyf hfe
          · have hadj' : G.Adj p.snd (Sym2.Mem.other hpsg) := by
              have hmem : s(p.snd, Sym2.Mem.other hpsg) ∈ G.edgeSet := by
                rw [hspec]; exact g.2
              exact (SimpleGraph.mem_edgeSet G).mp hmem
            have hne : Sym2.Mem.other hpsg ≠ v0 := by
              intro h
              apply hge; apply Subtype.ext
              rw [← hspec, h, he0v]; exact Sym2.eq_swap
            exact ⟨_, (hmemU _).mpr ⟨hne, hadj'⟩, hyf⟩
  11. The sum of degrees over U is at most 4: ∑_{w ∈ U} deg(w) ≤ 4.

    Since deg(p.snd) ≤ 3, removing v₀ gives |U| ≤ 2. At most one vertex in U has degree ≥ 2, and every vertex has degree at most 3. Bounding the sum by |U| plus 2 times the number of vertices of degree ≥ 2 yields at most 2 + 2(1) = 4.

    lines 136–161

    uses Finset.card_le_one, Finset.mem_filter, SimpleGraph.mem_neighborFinset, Finset.card_erase_of_mem, Finset.card_filter_add_card_filter_not, Finset.sum_le_sum, Finset.sum_add_distrib, Finset.sum_const, smul_eq_mul, mul_one, Finset.sum_filter, mul_comm

      have hsum : ∑ w ∈ (G.neighborFinset p.snd).erase v0, G.degree w ≤ 4 := by
        have hHcard : (((G.neighborFinset p.snd).erase v0).filter (fun w => 2 ≤ G.degree w)).card ≤ 1 := by
          rw [Finset.card_le_one]
          intro a ha b hb
          simp only [Finset.mem_filter] at ha hb
          by_contra hab
          rcases pairwise a ha.1 b hb.1 hab with h | h <;> omega
        have hUcard : ((G.neighborFinset p.snd).erase v0).card ≤ 2 := by
          have hmem : v0 ∈ G.neighborFinset p.snd := by
            rw [SimpleGraph.mem_neighborFinset]; exact hadj.symm
          rw [Finset.card_erase_of_mem hmem, G.card_neighborFinset_eq_degree]
          have := G.degree_le_maxDegree p.snd
          omega
        have hpart : (((G.neighborFinset p.snd).erase v0).filter (fun w => 2 ≤ G.degree w)).card
            + (((G.neighborFinset p.snd).erase v0).filter (fun w => ¬ 2 ≤ G.degree w)).card
            = ((G.neighborFinset p.snd).erase v0).card := Finset.card_filter_add_card_filter_not _
        calc ∑ w ∈ (G.neighborFinset p.snd).erase v0, G.degree w
            ≤ ∑ w ∈ (G.neighborFinset p.snd).erase v0, (1 + if 2 ≤ G.degree w then 2 else 0) :=
              Finset.sum_le_sum (fun w _ => by
                have := G.degree_le_maxDegree w
                split_ifs <;> omega)
          _ = ((G.neighborFinset p.snd).erase v0).card
              + 2 * (((G.neighborFinset p.snd).erase v0).filter (fun w => 2 ≤ G.degree w)).card := by
              rw [Finset.sum_add_distrib, Finset.sum_const, smul_eq_mul, mul_one, ← Finset.sum_filter,
                Finset.sum_const, smul_eq_mul, mul_comm]
          _ ≤ 4 := by omega
  12. The edge e₀ and leaf vertex v₀ satisfy the theorem.

    The vertex v₀ belongs to e₀ and has deg(v₀) = 1. Every edge at distance 1 or 2 from e₀ in the line graph is incident to some vertex in U, so the set of these edges injects into the union of incidence sets over w ∈ U. The cardinality is thus at most ∑_{w ∈ U} deg(w) ≤ 4.

    lines 162–177

    uses Sym2.mem_mk_left, Finset.card_le_card_of_injOn, Finset.mem_filter, Finset.mem_coe, Finset.mem_erase, Finset.mem_biUnion, SimpleGraph.mem_incidenceFinset, Subtype.ext, Finset.card_biUnion_le, Finset.sum_congr

      refine ⟨e0, v0, Sym2.mem_mk_left _ _, deg_v0, ?_⟩
      calc _ ≤ (((G.neighborFinset p.snd).erase v0).biUnion (fun w => G.incidenceFinset w)).card := by
            apply Finset.card_le_card_of_injOn (fun f : G.edgeSet => (f : Sym2 V))
            · intro f hf
              have hf' := Finset.mem_filter.mp (Finset.mem_coe.mp hf)
              have hfe : f ≠ e0 := (Finset.mem_erase.mp hf'.1).1
              obtain ⟨w, hw, hwf⟩ := cover f hfe hf'.2
              exact Finset.mem_coe.mpr (Finset.mem_biUnion.mpr
                ⟨w, hw, (SimpleGraph.mem_incidenceFinset G w _).mpr ⟨f.2, hwf⟩⟩)
            · intro a _ b _ h
              exact Subtype.ext h
        _ ≤ ∑ w ∈ (G.neighborFinset p.snd).erase v0, (G.incidenceFinset w).card := Finset.card_biUnion_le
        _ = ∑ w ∈ (G.neighborFinset p.snd).erase v0, G.degree w := by
            refine Finset.sum_congr rfl (fun w _ => ?_)
            exact G.card_incidenceFinset_eq_degree w
        _ ≤ 4 := hsum
maxDegree_le_two_exists_rich_neighbor_five_coloring_decRelLineGraphAdj
A line graph edge adjacency decidability instance for graphs of maximum degree at most 2.
maxDegree_le_two_exists_rich_neighbor_five_coloring
A theorem guaranteeing the existence of a rich-neighbor 5-coloring on graphs of maximum degree at most 2.
SimpleGraph.mem_edgeFinset
An edge belongs to the edge finset if and only if it belongs to the edge set.
Sym2.inductionOn
Induction principle on unordered pairs: a statement holds for all unordered pairs if it holds for pairs of the form s(x, y).
SimpleGraph.not_isDiag_of_mem_edgeSet
An edge in a simple graph is not diagonal, meaning its two endpoints are distinct.
SimpleGraph.Walk.exists_isPath_forall_isPath_length_le_length
In any nonempty graph with a finite edge set, there exists a simple path whose length is maximal among all simple paths.
Finite.of_fintype
Every type equipped with a Fintype instance is finite.
SimpleGraph.mem_edgeSet
An unordered pair s(v, w) belongs to the edge set if and only if v and w are adjacent.
SimpleGraph.Walk.IsPath.of_adj
The single-step walk along an edge is a simple path.
SimpleGraph.Walk.length_eq_zero_iff
A walk has length 0 if and only if it is the trivial walk Nil.
SimpleGraph.Walk.cons_tail_eq
A non-nil walk equals the step to its second vertex prepended to its tail walk.
SimpleGraph.Walk.support_cons
The vertex support of cons h p is the starting vertex prepended to the support of p.
List.mem_cons
An element belongs to b :: l if and only if it equals b or belongs to l.
SimpleGraph.degree_eq_one_iff_existsUnique_adj
A vertex has degree 1 if and only if it has a unique adjacent neighbor.
SimpleGraph.Walk.length_cons
Prepending an edge to a walk increases its length by 1.
List.mem_cons_of_mem
If an element belongs to a list l, it belongs to y :: l.
SimpleGraph.Walk.length_tail
The tail of a walk has length equal to the walk's length minus 1.
Finset.mem_erase
An element belongs to s.erase b if and only if it is not b and belongs to s.
SimpleGraph.mem_neighborFinset
A vertex w belongs to the neighbor finset of v if and only if v and w are adjacent.
Finset.card_eq_one
A finite set has cardinality 1 if and only if it is a singleton {x}.
SimpleGraph.mem_incidenceFinset
An edge belongs to the incidence finset of v if and only if it belongs to the incidence set of v.
Sym2.mem_mk_left
The first coordinate x belongs to the unordered pair s(x, y).
Finset.mem_singleton
An element belongs to {a} if and only if it equals a.
Subtype.ext
Two subtype terms are equal if and only if their underlying values are equal.
Sym2.mem_iff
An element belongs to s(b, c) if and only if it equals b or c.
Sym2.Mem.other
Given a vertex a in an unordered pair z, returns the other vertex of z.
Sym2.other_mem
The other vertex of an unordered pair z containing a also belongs to z.
Sym2.other_spec
An unordered pair z containing a is equal to s(a, other).
Sym2.eq_swap
The unordered pair s(a, b) equals s(b, a).
SimpleGraph.lineGraph_adj_iff_exists
Two edges are adjacent in the line graph if and only if they are distinct and share an endpoint.
Finset.card_le_one
A finset has cardinality at most 1 if and only if any two of its elements are equal.
Finset.mem_filter
An element belongs to Finset.filter p s if and only if it is in s and satisfies p.
Finset.card_erase_of_mem
Erasing an element from a finset decreases its cardinality by 1.
Finset.card_filter_add_card_filter_not
The size of a finset is the sum of the sizes of its elements satisfying p and those not satisfying p.
Finset.sum_le_sum
If f i ≤ g i for all i in a finset s, then the sum of f over s is at most the sum of g over s.
Finset.sum_add_distrib
The sum of (f + g) over a finset equals the sum of f plus the sum of g.
Finset.sum_const
The sum of a constant value over a finset equals the size of the finset times the constant.
smul_eq_mul
Scalar multiplication of natural numbers corresponds to multiplication.
mul_one
Multiplying a number by 1 leaves it unchanged.
Finset.sum_filter
Summing over a filtered finset equals summing an if-then-else over the original finset.
mul_comm
Multiplication is commutative.
Finset.card_le_card_of_injOn
If an injective function maps a finset s into a finset t, then |s| ≤ |t|.
Finset.mem_coe
An element belongs to the set coercion of a finset if and only if it belongs to the finset.
Finset.mem_biUnion
An element belongs to a finset biUnion if and only if it belongs to the image of some index element.
Finset.card_biUnion_le
The cardinality of a finset union is at most the sum of the cardinalities of the indexed sets.
Finset.sum_congr
Two sums over equal finsets with equal summands are equal.

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

/-- In any finite acyclic simple graph of maximum degree at most 3 with at least one edge, there exists an edge incident to a leaf vertex having at most 4 edges at distance 1 or 2 from it in the line graph. -/theorem subcubic_isAcyclic_exists_leaf_edge_dist_two_le_four {V : Type*}    [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj]    (hdeg : G.maxDegree ≤ 3) (hforest : G.IsAcyclic)    (hne : G.edgeFinset.Nonempty) :    ∃ (e : G.edgeSet) (v : V), v ∈ e.val ∧ G.degree v = 1 ∧      ((Finset.univ.erase e).filter (fun f : G.edgeSet =>        G.lineGraph.Adj e f ∨ ∃ g : G.edgeSet, G.lineGraph.Adj g e ∧ G.lineGraph.Adj g f)).card ≤ 4 := by  have _hinst := @maxDegree_le_two_exists_rich_neighbor_five_coloring_decRelLineGraphAdj V  clear _hinst  have _howner := @maxDegree_le_two_exists_rich_neighbor_five_coloring V  clear _howner  classical  have hV : Nonempty V := by    obtain ⟨e, he⟩ := hne    rw [SimpleGraph.mem_edgeFinset] at he    exact Sym2.inductionOn e (fun a b _ => ⟨a⟩) (SimpleGraph.not_isDiag_of_mem_edgeSet (G := G) he)  obtain ⟨v0, vk, p, hp, hmax⟩ :=    @SimpleGraph.Walk.exists_isPath_forall_isPath_length_le_length V G hV (Finite.of_fintype G.edgeSet)  have hK1 : 1 ≤ p.length := by    obtain ⟨e, he⟩ := hne    rw [SimpleGraph.mem_edgeFinset] at he    refine Sym2.inductionOn e (f := fun e => e ∈ G.edgeSet → 1 ≤ p.length) ?_ he    intro a b hmem    have hab : G.Adj a b := (SimpleGraph.mem_edgeSet G).mp hmem    have hpth : hab.toWalk.IsPath := SimpleGraph.Walk.IsPath.of_adj hab    have h := hmax a b hab.toWalk hpth    simpa using h  have hnil : ¬ p.Nil := by    rw [← SimpleGraph.Walk.length_eq_zero_iff]; omega  have hp_tail : p.tail.IsPath := hp.tail  have hadj : G.Adj v0 p.snd := p.adj_snd hnil  have hdecomp : p.support = v0 :: p.tail.support := by    conv_lhs => rw [← SimpleGraph.Walk.cons_tail_eq p hnil]    rw [SimpleGraph.Walk.support_cons]  have hsupp_tail_of : ∀ {w : V}, w ∈ p.support → w ≠ v0 → w ∈ p.tail.support := by    intro w hw hwv0    rw [hdecomp] at hw    rcases List.mem_cons.mp hw with h | h    · exact absurd h hwv0    · exact h  have start_leaf : ∀ {a b : V} (r : G.Walk a b), r.IsPath → r.length = p.length → G.degree a = 1 := by    intro a b r hr hrlen    have hrnil : ¬ r.Nil := by rw [← SimpleGraph.Walk.length_eq_zero_iff]; omega    rw [SimpleGraph.degree_eq_one_iff_existsUnique_adj]    refine ⟨r.snd, r.adj_snd hrnil, fun w hw => ?_⟩    by_cases hmem : w ∈ r.support    · exact hforest.eq_snd_of_adj_start hr hw hmem    · exfalso      have hp' : (r.cons hw.symm).IsPath := hr.cons hmem      have hlt := hmax w b (r.cons hw.symm) hp'      rw [SimpleGraph.Walk.length_cons, hrlen] at hlt      omega  have deg_v0 : G.degree v0 = 1 := start_leaf p hp rfl  have leaf_offpath : ∀ w : V, G.Adj p.snd w → w ∉ p.support → G.degree w = 1 := by    intro w hwu hwsupp    have hwt : w ∉ p.tail.support := fun h => hwsupp (by rw [hdecomp]; exact List.mem_cons_of_mem _ h)    have hpth : (p.tail.cons hwu.symm).IsPath := hp_tail.cons hwt    have hlen : (p.tail.cons hwu.symm).length = p.length := by      rw [SimpleGraph.Walk.length_cons, SimpleGraph.Walk.length_tail]; omega    exact start_leaf (p.tail.cons hwu.symm) hpth hlen  have onpath_eq : ∀ w : V, G.Adj p.snd w → w ∈ p.tail.support → w = p.tail.snd := by    intro w hwu hwt    exact hforest.eq_snd_of_adj_start hp_tail hwu hwt  have hmemU : ∀ w, w ∈ (G.neighborFinset p.snd).erase v0 ↔ w ≠ v0 ∧ G.Adj p.snd w := by    intro w; rw [Finset.mem_erase, SimpleGraph.mem_neighborFinset]  have pairwise : ∀ w1 ∈ (G.neighborFinset p.snd).erase v0, ∀ w2 ∈ (G.neighborFinset p.snd).erase v0,      w1 ≠ w2 → G.degree w1 = 1 ∨ G.degree w2 = 1 := by    intro w1 h1 w2 h2 hne12    obtain ⟨h1v, hadj1⟩ := (hmemU w1).mp h1    obtain ⟨h2v, hadj2⟩ := (hmemU w2).mp h2    by_cases hsup1 : w1 ∈ p.tail.support    · by_cases hsup2 : w2 ∈ p.tail.support      · exact absurd (by rw [onpath_eq w1 hadj1 hsup1, onpath_eq w2 hadj2 hsup2]) hne12      · right; exact leaf_offpath w2 hadj2 (fun h => hsup2 (hsupp_tail_of h h2v))    · left; exact leaf_offpath w1 hadj1 (fun h => hsup1 (hsupp_tail_of h h1v))  let e0 : G.edgeSet := ⟨s(v0, p.snd), (SimpleGraph.mem_edgeSet G).mpr hadj⟩  have he0v : (e0 : Sym2 V) = s(v0, p.snd) := rfl  have hinc_v0 : ∀ f : G.edgeSet, v0 ∈ (f : Sym2 V) → f = e0 := by    intro f hf    have hcard : (G.incidenceFinset v0).card = 1 := by      rw [G.card_incidenceFinset_eq_degree]; exact deg_v0    obtain ⟨x, hx⟩ := Finset.card_eq_one.mp hcard    have hxe : (e0 : Sym2 V) ∈ G.incidenceFinset v0 := by      rw [SimpleGraph.mem_incidenceFinset]; exact ⟨e0.2, by rw [he0v]; exact Sym2.mem_mk_left _ _⟩    rw [hx] at hxe    simp only [Finset.mem_singleton] at hxe    have hfmem : (f : Sym2 V) ∈ G.incidenceFinset v0 := by      rw [SimpleGraph.mem_incidenceFinset]; exact ⟨f.2, hf⟩    rw [hx] at hfmem    simp only [Finset.mem_singleton] at hfmem    exact Subtype.ext (hfmem.trans hxe.symm)  have share_e0 : ∀ g : G.edgeSet, (∃ x, x ∈ (e0 : Sym2 V) ∧ x ∈ (g : Sym2 V)) → g ≠ e0 → p.snd ∈ (g : Sym2 V) := by    intro g ⟨x, hxe0, hxg⟩ hge    have hx : x = v0 ∨ x = p.snd := by rw [he0v] at hxe0; exact Sym2.mem_iff.mp hxe0    rcases hx with rfl | rfl    · exact absurd (hinc_v0 g hxg) hge    · exact hxg  have incidence_step : ∀ f : G.edgeSet, p.snd ∈ (f : Sym2 V) → f ≠ e0 →      ∃ w ∈ (G.neighborFinset p.snd).erase v0, w ∈ (f : Sym2 V) := by    intro f hps hfe    refine ⟨Sym2.Mem.other hps, ?_, Sym2.other_mem hps⟩    have hadj' : G.Adj p.snd (Sym2.Mem.other hps) := by      have hmem : s(p.snd, Sym2.Mem.other hps) ∈ G.edgeSet := by        rw [Sym2.other_spec hps]; exact f.2      exact (SimpleGraph.mem_edgeSet G).mp hmem    have hne : Sym2.Mem.other hps ≠ v0 := by      intro h      apply hfe; apply Subtype.ext      rw [← Sym2.other_spec hps, h, he0v]; exact Sym2.eq_swap    exact (hmemU _).mpr ⟨hne, hadj'⟩  have cover : ∀ f : G.edgeSet, f ≠ e0 →      (G.lineGraph.Adj e0 f ∨ ∃ g : G.edgeSet, G.lineGraph.Adj g e0 ∧ G.lineGraph.Adj g f) →      ∃ w ∈ (G.neighborFinset p.snd).erase v0, w ∈ (f : Sym2 V) := by    intro f hfe hdist    rcases hdist with h1 | ⟨g, hg1, hg2⟩    · obtain ⟨_, x, hx0, hxf⟩ := (SimpleGraph.lineGraph_adj_iff_exists).mp h1      exact incidence_step f (share_e0 f ⟨x, hx0, hxf⟩ hfe) hfe    · obtain ⟨hge, x, hx0, hxg⟩ := (SimpleGraph.lineGraph_adj_iff_exists).mp hg1      obtain ⟨_, y, hyg, hyf⟩ := (SimpleGraph.lineGraph_adj_iff_exists).mp hg2      have hpsg : p.snd ∈ (g : Sym2 V) := share_e0 g ⟨x, hxg, hx0⟩ hge      have hspec : s(p.snd, Sym2.Mem.other hpsg) = (g : Sym2 V) := Sym2.other_spec hpsg      have hy : y = p.snd ∨ y = Sym2.Mem.other hpsg := by        rw [← hspec] at hyg; exact Sym2.mem_iff.mp hyg      rcases hy with rfl | rfl      · exact incidence_step f hyf hfe      · have hadj' : G.Adj p.snd (Sym2.Mem.other hpsg) := by          have hmem : s(p.snd, Sym2.Mem.other hpsg) ∈ G.edgeSet := by            rw [hspec]; exact g.2          exact (SimpleGraph.mem_edgeSet G).mp hmem        have hne : Sym2.Mem.other hpsg ≠ v0 := by          intro h          apply hge; apply Subtype.ext          rw [← hspec, h, he0v]; exact Sym2.eq_swap        exact ⟨_, (hmemU _).mpr ⟨hne, hadj'⟩, hyf⟩  have hsum : ∑ w ∈ (G.neighborFinset p.snd).erase v0, G.degree w ≤ 4 := by    have hHcard : (((G.neighborFinset p.snd).erase v0).filter (fun w => 2 ≤ G.degree w)).card ≤ 1 := by      rw [Finset.card_le_one]      intro a ha b hb      simp only [Finset.mem_filter] at ha hb      by_contra hab      rcases pairwise a ha.1 b hb.1 hab with h | h <;> omega    have hUcard : ((G.neighborFinset p.snd).erase v0).card ≤ 2 := by      have hmem : v0 ∈ G.neighborFinset p.snd := by        rw [SimpleGraph.mem_neighborFinset]; exact hadj.symm      rw [Finset.card_erase_of_mem hmem, G.card_neighborFinset_eq_degree]      have := G.degree_le_maxDegree p.snd      omega    have hpart : (((G.neighborFinset p.snd).erase v0).filter (fun w => 2 ≤ G.degree w)).card        + (((G.neighborFinset p.snd).erase v0).filter (fun w => ¬ 2 ≤ G.degree w)).card        = ((G.neighborFinset p.snd).erase v0).card := Finset.card_filter_add_card_filter_not _    calc ∑ w ∈ (G.neighborFinset p.snd).erase v0, G.degree w        ≤ ∑ w ∈ (G.neighborFinset p.snd).erase v0, (1 + if 2 ≤ G.degree w then 2 else 0) :=          Finset.sum_le_sum (fun w _ => by            have := G.degree_le_maxDegree w            split_ifs <;> omega)      _ = ((G.neighborFinset p.snd).erase v0).card          + 2 * (((G.neighborFinset p.snd).erase v0).filter (fun w => 2 ≤ G.degree w)).card := by          rw [Finset.sum_add_distrib, Finset.sum_const, smul_eq_mul, mul_one, ← Finset.sum_filter,            Finset.sum_const, smul_eq_mul, mul_comm]      _ ≤ 4 := by omega  refine ⟨e0, v0, Sym2.mem_mk_left _ _, deg_v0, ?_⟩  calc _ ≤ (((G.neighborFinset p.snd).erase v0).biUnion (fun w => G.incidenceFinset w)).card := by        apply Finset.card_le_card_of_injOn (fun f : G.edgeSet => (f : Sym2 V))        · intro f hf          have hf' := Finset.mem_filter.mp (Finset.mem_coe.mp hf)          have hfe : f ≠ e0 := (Finset.mem_erase.mp hf'.1).1          obtain ⟨w, hw, hwf⟩ := cover f hfe hf'.2          exact Finset.mem_coe.mpr (Finset.mem_biUnion.mpr            ⟨w, hw, (SimpleGraph.mem_incidenceFinset G w _).mpr ⟨f.2, hwf⟩⟩)        · intro a _ b _ h          exact Subtype.ext h    _ ≤ ∑ w ∈ (G.neighborFinset p.snd).erase v0, (G.incidenceFinset w).card := Finset.card_biUnion_le    _ = ∑ w ∈ (G.neighborFinset p.snd).erase v0, G.degree w := by        refine Finset.sum_congr rfl (fun w _ => ?_)        exact G.card_incidenceFinset_eq_degree w    _ ≤ 4 := hsum
See it in the graphDiscuss this resultChallenge it