digraph_is_subgraph_of
def
A directed graph G is a subgraph of H if there is an injective vertex map from V(G) to V(H) that sends every edge of G to an edge of H.
Statement
def digraph_is_subgraph_of {V W : Type*} (G : Digraph V) (H : Digraph W) : Prop
- Defined in
- arXiv:2610.18600 Section 3
- Verified
- 25 Oct 2026
- Axioms
- none listed
- Used by 1
- digraph_subgraph_fintype_card_leIf a finite directed graph G is a subgraph of a finite directed graph H, then the vertex count of G is at most the vertex count of H.
Read back from the Lean
Given types V and W, and directed graphs G on V and H on W, digraph_is_subgraph_of G H asserts that there exists a function f : V → W such that:
1. f is injective (∀ ⦃a₁ a₂ : V⦄, f a₁ = f a₂ → a₁ = a₂), and
2. For all u, v : V, if u is adjacent to v in G (G.Adj u v), then f u is adjacent to f v in H (H.Adj (f u) (f v)).
In other words, there exists an injective digraph homomorphism (a subgraph embedding) from G into H, meaning G is isomorphic to a subgraph of H.
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
/-- G is a subgraph of H if there is an injective map from V(G) to V(H) preserving directed edges. -/ def digraph_is_subgraph_of {V W : Type*} (G : Digraph V) (H : Digraph W) : Prop := ∃ f : V → W, Function.Injective f ∧ ∀ u v, G.Adj u v → H.Adj (f u) (f v)