tree_edge_disjoint_embedding_of_star_T
For n ≥ 2, if T is a spanning star tree on Fin n with center r, then every tree S on Fin (n - 1) can be embedded into Fin n edge-disjointly from T such that the union graph T ⊔ S.map φ is 2-degenerate.
Statement
theorem tree_edge_disjoint_embedding_of_star_T {n : ℕ} (hn : 2 ≤ n)
(T : SimpleGraph (Fin n)) (hT : T.IsTree) (r : Fin n) (hTr : T = SimpleGraph.starGraph r)
(S : SimpleGraph (Fin (n - 1))) (hS : S.IsTree) :
∃ φ : Fin (n - 1) ↪ Fin n,
Disjoint T (S.map φ) ∧ simple_graph_is_degenerate (T ⊔ S.map φ) 2- Source
- arXiv:2611.04674 Lemma 2.1 (Pair preparation)
- Verified
- 07 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- simple_graph_is_degenerateA simple graph G on a vertex type V is k-degenerate if for every nonempty subset of vertices s ⊆ V, there exists a vertex v ∈ s such that…
- supportThe support $\mathrm{supp}(p) \subseteq \mathrm{Fin}\,n$ consists of coordinates where $p(i) \neq I$; the weight is…
Read back from the Lean
Let $n$ be a natural number with $2 \le n$. Let $T$ be a simple graph on vertex set $\mathrm{Fin}(n)$ that is a tree, and let $r \in \mathrm{Fin}(n)$ such that $T$ is the star graph centered at $r$ (SimpleGraph.starGraph r). Let $S$ be a simple graph on vertex set $\mathrm{Fin}(n - 1)$ that is a tree.
Then there exists an injective map (embedding) $\varphi : \mathrm{Fin}(n - 1) \hookrightarrow \mathrm{Fin}(n)$ such that:
1. $T$ and the graph $S.\mathrm{map}(\varphi)$ are edge-disjoint (Disjoint T (S.map φ)).
2. The union graph $T \sqcup S.\mathrm{map}(\varphi)$ is 2-degenerate (i.e., simple_graph_is_degenerate (T ⊔ S.map φ) 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
Dummy summary
Dummy 1
Dummy 1
classical haveI : Nonempty s := hs.to_subtype obtain ⟨u, v, p, hp, hmax⟩ := SimpleGraph.Walk.exists_isPath_forall_isPath_length_le_length (H.induce s) have hacyc : (H.induce s).IsAcyclic := hH.induce s refine ⟨u.1, u.2, ?_⟩ have hsub : (s ∩ H.neighborSet u.1) ⊆ {p.snd.1} := by intro x hx obtain ⟨hxs, hxadj⟩ := hx have hadj : (H.induce s).Adj u ⟨x, hxs⟩ := by rw [SimpleGraph.induce_adj]; exact hxadj by_cases hmem : (⟨x, hxs⟩ : s) ∈ p.support · have := hacyc.eq_snd_of_adj_start hp hadj hmem simp only [Set.mem_singleton_iff] exact congrArg Subtype.val this · have hpath : (SimpleGraph.Walk.cons hadj.symm p).IsPath := hp.cons hmem have := hmax _ _ _ hpath rw [SimpleGraph.Walk.length_cons] at this omega calc (s ∩ H.neighborSet u.1).encard ≤ ({p.snd.1} : Set V).encard := Set.encard_mono hsub _ = 1 := Set.encard_singleton _
Dummy 2
Dummy 2
obtain ⟨m, rfl⟩ : ∃ m, n = m + 1 := ⟨n - 1, by omega⟩ subst hTr let Φ : Fin m ↪ Fin (m + 1) := ⟨fun i => r.succAbove i, Fin.succAbove_right_injective⟩ have hΦ : ∀ i, Φ i = r.succAbove i := fun i => rfl refine ⟨Φ, ?_, ?_⟩ · rw [disjoint_iff_inf_le, SimpleGraph.le_iff_adj] intro u v huv exfalso rw [SimpleGraph.inf_adj, SimpleGraph.starGraph_adj, SimpleGraph.map_adj] at huv obtain ⟨⟨-, hru | hrv⟩, ⟨a, b, -, ha, hb⟩⟩ := huv · refine Fin.succAbove_ne r a ?_ show Φ a = r rw [ha, hru] · refine Fin.succAbove_ne r b ?_ show Φ b = r rw [hb, hrv] · intro s hs by_cases hcase : ∃ x ∈ s, x ≠ r · obtain ⟨x, hxs, hxr⟩ := hcase have hxrange : x ∈ Set.range (fun i => r.succAbove i) := by rw [Fin.range_succAbove]; simpa using hxr obtain ⟨i, hi⟩ := hxrange have hsi : i ∈ Φ ⁻¹' s := by show (fun i => r.succAbove i) i ∈ s rw [hi]; exact hxs obtain ⟨j, hjt, hjc⟩ := tree_edge_disjoint_embedding_of_star_T_forest_exists_deg_le_one S hS.isAcyclic (s := Φ ⁻¹' s) ⟨i, hsi⟩ have hjt' : Φ j ∈ s := hjt refine ⟨Φ j, hjt', ?_⟩ have hsub : s ∩ (starGraph r ⊔ S.map Φ).neighborSet (Φ j) ⊆ insert r (Φ '' (Φ ⁻¹' s ∩ S.neighborSet j)) := by intro y hy obtain ⟨hys, hyadj⟩ := hy rw [SimpleGraph.mem_neighborSet, SimpleGraph.sup_adj] at hyadj rcases hyadj with hstar | hmap · rw [SimpleGraph.starGraph_adj] at hstar obtain ⟨-, h1 | h2⟩ := hstar · exact absurd (by rw [← hΦ j]; exact h1) (Fin.succAbove_ne r j) · exact Set.mem_insert_iff.mpr (Or.inl h2) · rw [SimpleGraph.map_adj] at hmap obtain ⟨a, b, hab, ha, hb⟩ := hmap have haj : a = j := Fin.succAbove_right_injective (show r.succAbove a = r.succAbove j by rw [← hΦ a, ← hΦ j]; exact ha) refine Set.mem_insert_iff.mpr (Or.inr ⟨b, ⟨?_, ?_⟩, hb⟩) · rw [Set.mem_preimage, hb]; exact hys · rw [haj] at hab; exact hab have hnotmem : r ∉ Φ '' (Φ ⁻¹' s ∩ S.neighborSet j) := by rintro ⟨b, -, hb⟩ refine Fin.succAbove_ne r b ?_ show Φ b = r exact hb have henc : (Φ '' (Φ ⁻¹' s ∩ S.neighborSet j)).encard = (Φ ⁻¹' s ∩ S.neighborSet j).encard := Function.Injective.encard_image Φ.injective _ calc (s ∩ (starGraph r ⊔ S.map Φ).neighborSet (Φ j)).encard ≤ (insert r (Φ '' (Φ ⁻¹' s ∩ S.neighborSet j))).encard := Set.encard_mono hsub _ = (Φ '' (Φ ⁻¹' s ∩ S.neighborSet j)).encard + 1 := Set.encard_insert_of_notMem hnotmem _ = (Φ ⁻¹' s ∩ S.neighborSet j).encard + 1 := by rw [henc] _ ≤ 1 + 1 := add_le_add hjc le_rfl _ = ((2 : ℕ) : ℕ∞) := by norm_num · push Not at hcase obtain ⟨x, hx⟩ := hs have hrs : r ∈ s := by rw [← hcase x hx]; exact hx refine ⟨r, hrs, ?_⟩ have hemp : s ∩ (starGraph r ⊔ S.map Φ).neighborSet r = ∅ := by rw [Set.eq_empty_iff_forall_notMem] rintro y ⟨hys, hyN⟩ rw [SimpleGraph.mem_neighborSet] at hyN exact (SimpleGraph.loopless _).irrefl r (hcase y hys ▸ hyN) rw [hemp] exact Set.encard_empty.le.trans (by simp)
- Unresolved check: step 1's explanation only repeats its claim: say how it is shown
- Unresolved check: step 2's explanation only repeats its claim: say how it is shown
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.
open SimpleGraphlemma tree_edge_disjoint_embedding_of_star_T_forest_exists_deg_le_one {V : Type*} [Finite V] (H : SimpleGraph V) (hH : H.IsAcyclic) {s : Set V} (hs : s.Nonempty) : ∃ v ∈ s, (s ∩ H.neighborSet v).encard ≤ 1 := by classical haveI : Nonempty s := hs.to_subtype obtain ⟨u, v, p, hp, hmax⟩ := SimpleGraph.Walk.exists_isPath_forall_isPath_length_le_length (H.induce s) have hacyc : (H.induce s).IsAcyclic := hH.induce s refine ⟨u.1, u.2, ?_⟩ have hsub : (s ∩ H.neighborSet u.1) ⊆ {p.snd.1} := by intro x hx obtain ⟨hxs, hxadj⟩ := hx have hadj : (H.induce s).Adj u ⟨x, hxs⟩ := by rw [SimpleGraph.induce_adj]; exact hxadj by_cases hmem : (⟨x, hxs⟩ : s) ∈ p.support · have := hacyc.eq_snd_of_adj_start hp hadj hmem simp only [Set.mem_singleton_iff] exact congrArg Subtype.val this · have hpath : (SimpleGraph.Walk.cons hadj.symm p).IsPath := hp.cons hmem have := hmax _ _ _ hpath rw [SimpleGraph.Walk.length_cons] at this omega calc (s ∩ H.neighborSet u.1).encard ≤ ({p.snd.1} : Set V).encard := Set.encard_mono hsub _ = 1 := Set.encard_singleton _/-- When the host spanning tree is a star, any tree of order n-1 can be packed edge-disjointly with 2-degenerate union. -/theorem tree_edge_disjoint_embedding_of_star_T {n : ℕ} (hn : 2 ≤ n) (T : SimpleGraph (Fin n)) (hT : T.IsTree) (r : Fin n) (hTr : T = SimpleGraph.starGraph r) (S : SimpleGraph (Fin (n - 1))) (hS : S.IsTree) : ∃ φ : Fin (n - 1) ↪ Fin n, Disjoint T (S.map φ) ∧ simple_graph_is_degenerate (T ⊔ S.map φ) 2 := by obtain ⟨m, rfl⟩ : ∃ m, n = m + 1 := ⟨n - 1, by omega⟩ subst hTr let Φ : Fin m ↪ Fin (m + 1) := ⟨fun i => r.succAbove i, Fin.succAbove_right_injective⟩ have hΦ : ∀ i, Φ i = r.succAbove i := fun i => rfl refine ⟨Φ, ?_, ?_⟩ · rw [disjoint_iff_inf_le, SimpleGraph.le_iff_adj] intro u v huv exfalso rw [SimpleGraph.inf_adj, SimpleGraph.starGraph_adj, SimpleGraph.map_adj] at huv obtain ⟨⟨-, hru | hrv⟩, ⟨a, b, -, ha, hb⟩⟩ := huv · refine Fin.succAbove_ne r a ?_ show Φ a = r rw [ha, hru] · refine Fin.succAbove_ne r b ?_ show Φ b = r rw [hb, hrv] · intro s hs by_cases hcase : ∃ x ∈ s, x ≠ r · obtain ⟨x, hxs, hxr⟩ := hcase have hxrange : x ∈ Set.range (fun i => r.succAbove i) := by rw [Fin.range_succAbove]; simpa using hxr obtain ⟨i, hi⟩ := hxrange have hsi : i ∈ Φ ⁻¹' s := by show (fun i => r.succAbove i) i ∈ s rw [hi]; exact hxs obtain ⟨j, hjt, hjc⟩ := tree_edge_disjoint_embedding_of_star_T_forest_exists_deg_le_one S hS.isAcyclic (s := Φ ⁻¹' s) ⟨i, hsi⟩ have hjt' : Φ j ∈ s := hjt refine ⟨Φ j, hjt', ?_⟩ have hsub : s ∩ (starGraph r ⊔ S.map Φ).neighborSet (Φ j) ⊆ insert r (Φ '' (Φ ⁻¹' s ∩ S.neighborSet j)) := by intro y hy obtain ⟨hys, hyadj⟩ := hy rw [SimpleGraph.mem_neighborSet, SimpleGraph.sup_adj] at hyadj rcases hyadj with hstar | hmap · rw [SimpleGraph.starGraph_adj] at hstar obtain ⟨-, h1 | h2⟩ := hstar · exact absurd (by rw [← hΦ j]; exact h1) (Fin.succAbove_ne r j) · exact Set.mem_insert_iff.mpr (Or.inl h2) · rw [SimpleGraph.map_adj] at hmap obtain ⟨a, b, hab, ha, hb⟩ := hmap have haj : a = j := Fin.succAbove_right_injective (show r.succAbove a = r.succAbove j by rw [← hΦ a, ← hΦ j]; exact ha) refine Set.mem_insert_iff.mpr (Or.inr ⟨b, ⟨?_, ?_⟩, hb⟩) · rw [Set.mem_preimage, hb]; exact hys · rw [haj] at hab; exact hab have hnotmem : r ∉ Φ '' (Φ ⁻¹' s ∩ S.neighborSet j) := by rintro ⟨b, -, hb⟩ refine Fin.succAbove_ne r b ?_ show Φ b = r exact hb have henc : (Φ '' (Φ ⁻¹' s ∩ S.neighborSet j)).encard = (Φ ⁻¹' s ∩ S.neighborSet j).encard := Function.Injective.encard_image Φ.injective _ calc (s ∩ (starGraph r ⊔ S.map Φ).neighborSet (Φ j)).encard ≤ (insert r (Φ '' (Φ ⁻¹' s ∩ S.neighborSet j))).encard := Set.encard_mono hsub _ = (Φ '' (Φ ⁻¹' s ∩ S.neighborSet j)).encard + 1 := Set.encard_insert_of_notMem hnotmem _ = (Φ ⁻¹' s ∩ S.neighborSet j).encard + 1 := by rw [henc] _ ≤ 1 + 1 := add_le_add hjc le_rfl _ = ((2 : ℕ) : ℕ∞) := by norm_num · push Not at hcase obtain ⟨x, hx⟩ := hs have hrs : r ∈ s := by rw [← hcase x hx]; exact hx refine ⟨r, hrs, ?_⟩ have hemp : s ∩ (starGraph r ⊔ S.map Φ).neighborSet r = ∅ := by rw [Set.eq_empty_iff_forall_notMem] rintro y ⟨hys, hyN⟩ rw [SimpleGraph.mem_neighborSet] at hyN exact (SimpleGraph.loopless _).irrefl r (hcase y hys ▸ hyN) rw [hemp] exact Set.encard_empty.le.trans (by simp)