AFTD Auto-Formalizing Theoretical Domains

tree_edge_disjoint_embedding_two_degenerate_union_two

theoremverified

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.

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

    line 7

    uses Subsingleton.elim

      let φ : Fin 1 ↪ Fin 2 := ⟨fun _ => 0, fun a b _ => Subsingleton.elim a b⟩
  2. 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).

    lines 8–14

    uses SimpleGraph.map_adj, SimpleGraph.bot_adj, iff_false, Subsingleton.elim

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

    lines 15–17

    uses disjoint_bot_right

      refine ⟨φ, ?_, ?_⟩
      · rw [hS_map]
        exact disjoint_bot_right
  4. 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.

    lines 18–21

    uses sup_bot_eq

      · rw [hS_map, sup_bot_eq]
        intro s hs
        obtain ⟨v, hv⟩ := hs
        refine ⟨v, hv, ?_⟩
  5. 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.

    lines 22–25

    uses Set.encard_le_encard, Set.subset_univ

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

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

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