AFTD Auto-Formalizing Theoretical Domains

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