is_edge_geodesic_transversal
A finite set S of edges of G is an edge geodesic transversal if every maximal geodesic in G contains at least one edge of S.
Statement
def is_edge_geodesic_transversal {V : Type*} (G : SimpleGraph V) (S : Finset (Sym2 V)) : Prop
- Defined in
- arXiv:2610.36821 Section 1
- Verified
- 28 Oct 2026
- Axioms
- none listed
- Used by 9
- edge_geodesic_transversal_bound_of_edge_cutLet G be a connected simple graph. Let S be a finite set of edges of G that is an edge cut induced by a vertex subset X (meaning there…
- edge_cut_transversal_theoremLet G be a connected simple graph. Let S be a finite set of edges of G of cardinality k that is an edge cut induced by a vertex subset X…
- edge_geodesic_transversal_numberThe edge geodesic transversal number of a simple graph G is the infimum in ℕ of the set of natural numbers k such that there exists a…
- geodesic_transversal_number_le_edge_geodesic_transversal_numberFor any connected simple graph G that admits a finite edge geodesic transversal, the vertex geodesic transversal number of G is bounded…
- corona_k1_exists_edge_geodesic_transversalFor every finite type V with 2 ≤ Fintype.card V and every connected simple graph G on V, there exists a finset S of edges of the corona…
- not_edge_geodesic_transversal_bound_of_edge_disjointThe statement
edge_geodesic_transversal_bound_of_edge_disjointis false: The statement is false as formalized because it omits a… - exists_geodesic_transversal_of_edge_geodesic_transversalFor any finite edge geodesic transversal T in a simple graph G, there exists a finite vertex geodesic transversal S of G such that the…
- edge_geodesic_transversal_number_corona_k1_card_twoFor every finite type V with Fintype.card V = 2 and every connected simple graph G on V, the edge geodesic transversal number of the…
- edge_geodesic_transversal_number_corona_k1_leFor every finite type V with 2 ≤ Fintype.card V and every connected simple graph G on V, the edge geodesic transversal number of the…
Read back from the Lean
For a type V, a simple graph G on V, and a finite set S of unordered pairs of vertices (Sym2 V), is_edge_geodesic_transversal G S asserts that:
1. Every element e ∈ S is an edge of G (e ∈ G.edgeSet).
2. For all vertices u, v : V and every walk p in G from u to v, if:
- p is a path (p.IsPath),
- the length of p equals the graph distance between u and v (p.length = G.dist u v),
- for every vertex w adjacent to u, G.dist w v ≤ p.length, and
- for every vertex w adjacent to v, G.dist u w ≤ p.length,
then there exists an edge e ∈ S that appears in p.edges.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- A finite set of edges S in G is an edge geodesic transversal if every maximal geodesic of G contains at least one edge of S. -/ def is_edge_geodesic_transversal {V : Type*} (G : SimpleGraph V) (S : Finset (Sym2 V)) : Prop := (∀ e ∈ S, e ∈ G.edgeSet) ∧ ∀ ⦃u v : V⦄ (p : G.Walk u v), (p.IsPath ∧ p.length = G.dist u v ∧ (∀ w, G.Adj w u → G.dist w v ≤ p.length) ∧ (∀ w, G.Adj v w → G.dist u w ≤ p.length)) → ∃ e ∈ S, e ∈ p.edges