simple_graph_leaf_edge_neighbors_adj
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
- simple_graph_strong_five_edge_coloring_extend_leaf_of_ncardGiven a leaf edge e of G with at most 4 other edges within distance 2 of e in the line graph (counted with Set.ncard), any strong…
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.
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.
uses
SimpleGraph.degree_eq_one_iff_existsUnique_adj,Sym2.mem_iff_exists.mp,SimpleGraph.mem_edgeSet,Subtype.extrw [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])
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.
uses
SimpleGraph.lineGraph_adj_iff_existsrw [SimpleGraph.lineGraph_adj_iff_exists] at hf hg ⊢ obtain ⟨hef, x, hxe, hxf⟩ := hf obtain ⟨heg, y, hye, hyg⟩ := hg
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.
uses
SimpleGraph.degree_eq_one_iff_existsUnique_adj,Sym2.mem_iff_exists.mp,SimpleGraph.mem_edgeSetobtain ⟨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]
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.
uses
Sym2.mem_iffhave 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
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.
uses
simple_graph_leaf_edge_neighbors_adj_edge_eq_of_mem_of_degree_eq_onehave 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
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.
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
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.
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⟩