subcubic_isAcyclic_exists_leaf_edge_dist_two_le_four
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
- maxDegree_le_two_exists_rich_neighbor_five_coloringEvery finite simple graph of maximum degree at most 2 admits a rich-neighbor 5-edge-colouring.
- simple_graph_is_rich_neighbor_coloringA proper edge colouring is a rich-neighbor edge colouring if every non-isolated edge (one with at least one adjacent edge) is adjacent to…
- Used by 2
- subcubic_isAcyclic_exists_strong_five_edge_coloringEvery finite simple graph of maximum degree at most 3 that is acyclic admits a strong 5-edge-coloring (where all edges are rich).
- subcubic_isAcyclic_exists_rich_neighbor_five_coloringEvery subcubic acyclic finite simple graph admits a rich-neighbor 5-edge-colouring.
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.
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.
uses
maxDegree_le_two_exists_rich_neighbor_five_coloring_decRelLineGraphAdj,maxDegree_le_two_exists_rich_neighbor_five_coloringhave _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
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.
uses
SimpleGraph.mem_edgeFinset,Sym2.inductionOn,SimpleGraph.not_isDiag_of_mem_edgeSethave 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)
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.
uses
SimpleGraph.Walk.exists_isPath_forall_isPath_length_le_length,Finite.of_fintypeobtain ⟨v0, vk, p, hp, hmax⟩ := @SimpleGraph.Walk.exists_isPath_forall_isPath_length_le_length V G hV (Finite.of_fintype G.edgeSet)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.
uses
SimpleGraph.mem_edgeFinset,Sym2.inductionOn,SimpleGraph.mem_edgeSet,SimpleGraph.Walk.IsPath.of_adj,SimpleGraph.Walk.length_eq_zero_iffhave 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
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.
uses
SimpleGraph.Walk.cons_tail_eq,SimpleGraph.Walk.support_cons,List.mem_conshave 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
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.
uses
SimpleGraph.Walk.length_eq_zero_iff,SimpleGraph.degree_eq_one_iff_existsUnique_adj,SimpleGraph.Walk.length_conshave 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
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.
uses
List.mem_cons_of_mem,SimpleGraph.Walk.length_cons,SimpleGraph.Walk.length_tailhave 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
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.
uses
Finset.mem_erase,SimpleGraph.mem_neighborFinsethave 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))
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.
uses
SimpleGraph.mem_edgeSet,Finset.card_eq_one,SimpleGraph.mem_incidenceFinset,Sym2.mem_mk_left,Finset.mem_singleton,Subtype.ext,Sym2.mem_ifflet 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
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.
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_iffhave 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⟩
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.
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_commhave 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
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.
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_congrrefine ⟨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.
- Lines 9–12 introduce and immediately clear two unused hypotheses (_hinst and _howner) concerning graph colorings; these are formal artifacts from the surrounding development that play no mathematical role in the argument.
- Several minor arithmetic steps, such as deducing that a path of length ≥ 1 is non-nil and evaluating the final degree sum bounds, are discharged by the automated linear arithmetic tactic omega.
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.
/-- 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