tree_edge_disjoint_embedding_two_degenerate_union_two
For n = 2, any tree S on Fin 1 can be embedded into Fin 2 edge-disjointly from a spanning tree T on Fin 2 such that the union graph T ⊔ S.map φ is 2-degenerate.
Statement
theorem tree_edge_disjoint_embedding_two_degenerate_union_two
(T : SimpleGraph (Fin 2)) (hT : T.IsTree)
(S : SimpleGraph (Fin 1)) (hS : S.IsTree) :
∃ φ : Fin 1 ↪ Fin 2,
Disjoint T (S.map φ) ∧ simple_graph_is_degenerate (T ⊔ S.map φ) 2- Source
- arXiv:2611.04674, Lemma 2.1
- Verified
- 05 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- 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…
Read back from the Lean
Given a simple graph T on Fin 2 that is a tree and a simple graph S on Fin 1 that is a tree, there exists an embedding (injective map) φ : Fin 1 ↪ Fin 2 such that: 1. T and the pushforward graph S.map φ are edge-disjoint (Disjoint T (S.map φ)), and 2. the graph union T ⊔ S.map φ is 2-degenerate (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
The embedding φ : Fin 1 ↪ Fin 2 is defined by mapping the unique vertex of Fin 1 to 0. Since simple graphs cannot contain loops and Fin 1 has only one vertex, S has no edges, so the pushforward graph S.map φ is the empty graph ⊥. As a result, S.map φ is trivially edge-disjoint from T, and their union reduces to T ⊔ ⊥ = T. Finally, T is 2-degenerate because every vertex in any nonempty subset s ⊆ Fin 2 has at most 2 neighbors in total, bounded by the ambient vertex set size |Fin 2| = 2.
Define an embedding φ : Fin 1 ↪ Fin 2 sending the single vertex of Fin 1 to 0.
Since Fin 1 contains only one element, the constant function sending that element to 0 is vacuously injective by Subsingleton.elim.
uses
Subsingleton.elimlet φ : Fin 1 ↪ Fin 2 := ⟨fun _ => 0, fun a b _ => Subsingleton.elim a b⟩
The embedded graph S.map φ is the empty graph ⊥ on Fin 2.
By extensionality on adjacency, we rewrite with SimpleGraph.map_adj, SimpleGraph.bot_adj, and iff_false. An edge in S.map φ between u and v would require an edge in S between two vertices x, y ∈ Fin 1. But Fin 1 has only one element (Subsingleton.elim), forcing x = y, which contradicts the irreflexivity of adjacency in simple graphs (S has no loops).
uses
SimpleGraph.map_adj,SimpleGraph.bot_adj,iff_false,Subsingleton.elimhave hS_map : S.map φ = ⊥ := by ext u v simp only [SimpleGraph.map_adj, SimpleGraph.bot_adj, iff_false] rintro ⟨x, y, hAdj, -⟩ have : x = y := Subsingleton.elim x y subst this exact S.irrefl hAdj
Witness the embedding with φ and deduce that T and S.map φ are edge-disjoint.
We supply φ as the witness. Since S.map φ = ⊥, the disjointness goal Disjoint T (S.map φ) reduces to Disjoint T ⊥, which holds by disjoint_bot_right.
uses
disjoint_bot_rightrefine ⟨φ, ?_, ?_⟩ · rw [hS_map] exact disjoint_bot_right
Simplify the union T ⊔ S.map φ to T, and select an arbitrary vertex v from any nonempty subset s ⊆ Fin 2.
Because S.map φ = ⊥, the union simplifies by sup_bot_eq to T. By definition of 2-degeneracy, for any nonempty set of vertices s ⊆ Fin 2, we must find a vertex in s with at most 2 neighbors in s. We pick an arbitrary vertex v ∈ s.
uses
sup_bot_eq· rw [hS_map, sup_bot_eq] intro s hs obtain ⟨v, hv⟩ := hs refine ⟨v, hv, ?_⟩
The number of neighbors of v in s is at most 2.
The set of neighbors s ∩ N_T(v) is a subset of the entire vertex set Fin 2, so its extended cardinality is bounded by |Fin 2| via Set.encard_le_encard and Set.subset_univ. Since Fin 2 has 2 elements, its extended cardinality is 2, satisfying the 2-degeneracy condition.
uses
Set.encard_le_encard,Set.subset_univhave h1 : (s ∩ T.neighborSet v).encard ≤ (Set.univ : Set (Fin 2)).encard := Set.encard_le_encard (Set.subset_univ _) have h2 : (Set.univ : Set (Fin 2)).encard = 2 := by simp rwa [h2] at h1
Subsingleton.elim- In a type with at most one element, any two elements are equal.
SimpleGraph.map_adj- Two vertices are adjacent in a pushforward graph if and only if they are the images of adjacent vertices in the original graph.
SimpleGraph.bot_adj- No two vertices are adjacent in the empty graph (the bottom element of the graph lattice).
iff_false- A proposition is equivalent to False if and only if its negation holds.
disjoint_bot_right- In any bounded order, every element is disjoint from the bottom element.
sup_bot_eq- The supremum (union) of any element with the bottom element is the element itself.
Set.encard_le_encard- If one set is a subset of another, its extended cardinality is at most that of the superset.
Set.subset_univ- Every set is a subset of the universal set of its ambient type.
- The tree hypotheses on T and S are not needed for the proof: any simple graph on 1 vertex is edge-free, and any simple graph on 2 vertices is trivially 2-degenerate because every vertex has degree at most 1.
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.
/-- Base case n = 2 of Lemma 2.1: any tree on 1 vertex can be embedded into K_2 disjointly from a spanning tree on 2 vertices with 2-degenerate union. -/theorem tree_edge_disjoint_embedding_two_degenerate_union_two (T : SimpleGraph (Fin 2)) (hT : T.IsTree) (S : SimpleGraph (Fin 1)) (hS : S.IsTree) : ∃ φ : Fin 1 ↪ Fin 2, Disjoint T (S.map φ) ∧ simple_graph_is_degenerate (T ⊔ S.map φ) 2 := by let φ : Fin 1 ↪ Fin 2 := ⟨fun _ => 0, fun a b _ => Subsingleton.elim a b⟩ have hS_map : S.map φ = ⊥ := by ext u v simp only [SimpleGraph.map_adj, SimpleGraph.bot_adj, iff_false] rintro ⟨x, y, hAdj, -⟩ have : x = y := Subsingleton.elim x y subst this exact S.irrefl hAdj refine ⟨φ, ?_, ?_⟩ · rw [hS_map] exact disjoint_bot_right · rw [hS_map, sup_bot_eq] intro s hs obtain ⟨v, hv⟩ := hs refine ⟨v, hv, ?_⟩ have h1 : (s ∩ T.neighborSet v).encard ≤ (Set.univ : Set (Fin 2)).encard := Set.encard_le_encard (Set.subset_univ _) have h2 : (Set.univ : Set (Fin 2)).encard = 2 := by simp rwa [h2] at h1