AFTD Auto-Formalizing Theoretical Domains

simple_graph_leaf_edge_neighbors_adj

theoremverified

Any two distinct lineGraph neighbors of a leaf edge e in G are adjacent in the line graph, because both must share the non-leaf endpoint of e.

Statement

theorem simple_graph_leaf_edge_neighbors_adj {V : Type*} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) [DecidableRel G.Adj]
    (e : G.edgeSet) (v : V) (hv : v ∈ e.val) (hleaf : G.degree v = 1)
    (f g : G.edgeSet) (hf : G.lineGraph.Adj e f) (hg : G.lineGraph.Adj e g) (hfg : f ≠ g) :
    G.lineGraph.Adj f g
Source
step towards simple_graph_strong_five_edge_coloring_extend_leaf
Verified
23 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1

The proof, explained

Because v has degree 1 in G, it has a unique neighbor w, so the edge e has endpoints v and w. Since f and g are distinct line-graph neighbors of e, each shares an endpoint with e, but neither can share v because e is the unique edge incident to v. Consequently, both f and g must share the other endpoint w with e. As f and g are distinct edges that both contain w, they share a vertex and are therefore adjacent in the line graph.

  1. Any two edges containing a vertex of degree 1 are equal.

    Since v has degree 1, it has a unique neighbor w in G. Any edges e and f containing v can be written as unordered pairs s(v, a) and s(v, b). Because e and f are edges of G, both a and b are adjacent to v, so by uniqueness of the neighbor of v, a = w and b = w. Thus e and f have the same endpoints {v, w}, making them equal.

    lines 6–12

    uses SimpleGraph.degree_eq_one_iff_existsUnique_adj, Sym2.mem_iff_exists.mp, SimpleGraph.mem_edgeSet, Subtype.ext

      rw [SimpleGraph.degree_eq_one_iff_existsUnique_adj] at hleaf
      obtain ⟨w, _, huniq⟩ := hleaf
      obtain ⟨a, ha⟩ := Sym2.mem_iff_exists.mp he
      obtain ⟨b, hb⟩ := Sym2.mem_iff_exists.mp hf
      have haA : G.Adj v a := (SimpleGraph.mem_edgeSet G).mp (ha ▸ e.property)
      have hbA : G.Adj v b := (SimpleGraph.mem_edgeSet G).mp (hb ▸ f.property)
      exact Subtype.ext (by rw [ha, hb, huniq a haA, huniq b hbA])
  2. Unpack the line-graph adjacency assumptions into shared vertices.

    By definition, two edges are adjacent in the line graph if and only if they are distinct and share at least one vertex. Applying this characterization to the hypotheses that e is adjacent to f and to g yields vertices x ∈ e ∩ f with e ≠ f, and y ∈ e ∩ g with e ≠ g.

    lines 20–22

    uses SimpleGraph.lineGraph_adj_iff_exists

      rw [SimpleGraph.lineGraph_adj_iff_exists] at hf hg ⊢
      obtain ⟨hef, x, hxe, hxf⟩ := hf
      obtain ⟨heg, y, hye, hyg⟩ := hg
  3. The edge e connects v to its unique neighbor w.

    Because v has degree 1, there is a unique vertex w adjacent to v. Since v ∈ e, the edge e can be written as s(v, a) for some vertex a. As e is an edge of G, v is adjacent to a, which by uniqueness forces a = w. Hence e has endpoints v and w.

    lines 23–27

    uses SimpleGraph.degree_eq_one_iff_existsUnique_adj, Sym2.mem_iff_exists.mp, SimpleGraph.mem_edgeSet

      obtain ⟨w, _, huniq⟩ := (SimpleGraph.degree_eq_one_iff_existsUnique_adj (G := G) (v := v)).mp hleaf
      obtain ⟨a, ha⟩ := Sym2.mem_iff_exists.mp hv
      have haA : G.Adj v a := (SimpleGraph.mem_edgeSet G).mp (ha ▸ e.property)
      have haw : a = w := huniq a haA
      have hew : e.val = s(v, w) := by rw [ha, haw]
  4. Any vertex of e other than v must be w.

    Since e has endpoints v and w, any vertex z ∈ e satisfies z = v or z = w. Therefore, if z ≠ v, then z = w.

    lines 28–31

    uses Sym2.mem_iff

      have key : ∀ z : V, z ∈ e.val → z ≠ v → z = w := by
        intro z hz hzv
        rw [hew, Sym2.mem_iff] at hz
        exact hz.resolve_left hzv
  5. Neither shared vertex x nor y can be the leaf vertex v.

    If x = v, then v ∈ f. Since v ∈ e and v has degree 1, the helper lemma implies f = e, which contradicts e ≠ f. Thus x ≠ v. By the exact same reasoning, assuming y = v implies g = e, contradicting e ≠ g, so y ≠ v.

    lines 32–39

    uses simple_graph_leaf_edge_neighbors_adj_edge_eq_of_mem_of_degree_eq_one

      have hxv : x ≠ v := by
        intro hxv
        exact hef (simple_graph_leaf_edge_neighbors_adj_edge_eq_of_mem_of_degree_eq_one
          G f e v hleaf (hxv ▸ hxf) hv).symm
      have hyv : y ≠ v := by
        intro hyv
        exact heg (simple_graph_leaf_edge_neighbors_adj_edge_eq_of_mem_of_degree_eq_one
          G g e v hleaf (hyv ▸ hyg) hv).symm
  6. f and g are adjacent in the line graph.

    Since x ∈ e and x ≠ v, the key property implies x = w, so w ∈ f. Likewise, since y ∈ e and y ≠ v, y = w, so w ∈ g. Thus both f and g contain the vertex w. Because f ≠ g by hypothesis, f and g are distinct edges sharing a vertex, and therefore they are adjacent in the line graph.

    line 40

      exact ⟨hfg, w, (key x hxe hxv) ▸ hxf, (key y hye hyv) ▸ hyg⟩
SimpleGraph.degree_eq_one_iff_existsUnique_adj
A vertex in a simple graph has degree 1 if and only if it has a unique adjacent vertex.
SimpleGraph.lineGraph_adj_iff_exists
Two edges are adjacent in the line graph if and only if they are distinct and share at least one vertex.
SimpleGraph.mem_edgeSet
An unordered pair of vertices belongs to the edge set of a simple graph if and only if the two vertices are adjacent in the graph.
Subtype.ext
Two terms of a subtype are equal if their underlying values are equal.
Sym2.mem_iff
An element belongs to the unordered pair s(b, c) if and only if it equals b or equals c.
Sym2.mem_iff_exists.mp
If a vertex belongs to an unordered pair, then the pair can be written as that vertex paired with some other vertex.
simple_graph_leaf_edge_neighbors_adj_edge_eq_of_mem_of_degree_eq_one
If a vertex has degree 1 in a simple graph, then any two edges containing that vertex 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

lemma simple_graph_leaf_edge_neighbors_adj_edge_eq_of_mem_of_degree_eq_one    {V : Type*} [Fintype V] [DecidableEq V]    (G : SimpleGraph V) [DecidableRel G.Adj]    (e f : G.edgeSet) (v : V) (hleaf : G.degree v = 1) (he : v ∈ e.val) (hf : v ∈ f.val) :    e = f := by  rw [SimpleGraph.degree_eq_one_iff_existsUnique_adj] at hleaf  obtain ⟨w, _, huniq⟩ := hleaf  obtain ⟨a, ha⟩ := Sym2.mem_iff_exists.mp he  obtain ⟨b, hb⟩ := Sym2.mem_iff_exists.mp hf  have haA : G.Adj v a := (SimpleGraph.mem_edgeSet G).mp (ha ▸ e.property)  have hbA : G.Adj v b := (SimpleGraph.mem_edgeSet G).mp (hb ▸ f.property)  exact Subtype.ext (by rw [ha, hb, huniq a haA, huniq b hbA])/-- Any two distinct lineGraph neighbors of a leaf edge e in G are adjacent in the line graph, because both must share the non-leaf endpoint of e. -/theorem simple_graph_leaf_edge_neighbors_adj {V : Type*} [Fintype V] [DecidableEq V]    (G : SimpleGraph V) [DecidableRel G.Adj]    (e : G.edgeSet) (v : V) (hv : v ∈ e.val) (hleaf : G.degree v = 1)    (f g : G.edgeSet) (hf : G.lineGraph.Adj e f) (hg : G.lineGraph.Adj e g) (hfg : f ≠ g) :    G.lineGraph.Adj f g := by  rw [SimpleGraph.lineGraph_adj_iff_exists] at hf hg ⊢  obtain ⟨hef, x, hxe, hxf⟩ := hf  obtain ⟨heg, y, hye, hyg⟩ := hg  obtain ⟨w, _, huniq⟩ := (SimpleGraph.degree_eq_one_iff_existsUnique_adj (G := G) (v := v)).mp hleaf  obtain ⟨a, ha⟩ := Sym2.mem_iff_exists.mp hv  have haA : G.Adj v a := (SimpleGraph.mem_edgeSet G).mp (ha ▸ e.property)  have haw : a = w := huniq a haA  have hew : e.val = s(v, w) := by rw [ha, haw]  have key : ∀ z : V, z ∈ e.val → z ≠ v → z = w := by    intro z hz hzv    rw [hew, Sym2.mem_iff] at hz    exact hz.resolve_left hzv  have hxv : x ≠ v := by    intro hxv    exact hef (simple_graph_leaf_edge_neighbors_adj_edge_eq_of_mem_of_degree_eq_one      G f e v hleaf (hxv ▸ hxf) hv).symm  have hyv : y ≠ v := by    intro hyv    exact heg (simple_graph_leaf_edge_neighbors_adj_edge_eq_of_mem_of_degree_eq_one      G g e v hleaf (hyv ▸ hyg) hv).symm  exact ⟨hfg, w, (key x hxe hxv) ▸ hxf, (key y hye hyv) ▸ hyg⟩
See it in the graphDiscuss this resultChallenge it