AFTD Auto-Formalizing Theoretical Domains

digraph_subgraph_fintype_card_le

theoremverified

If 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.

Statement

theorem digraph_subgraph_fintype_card_le {V W : Type*} [Fintype V] [Fintype W] {G : Digraph V} {H : Digraph W} (h : digraph_is_subgraph_of G H) : Fintype.card V ≤ Fintype.card W
Source
folklore
Verified
26 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • digraph_is_subgraph_ofA 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.

Read back from the Lean

For any types V and W with finite cardinality (instances [Fintype V] and [Fintype W]), and any directed graphs G on V and H on W: if G is a subgraph of H in the sense that there exists an injective function f : V → W mapping edges of G to edges of H (for all u, v : V, if G.Adj u v then H.Adj (f u) (f v)), then the cardinality of V is less than or equal to the cardinality of W (Fintype.card V ≤ Fintype.card W).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

By definition, a directed graph embedding of $G$ into $H$ provides an injective map from the vertex set $V$ of $G$ to the vertex set $W$ of $H$. The existence of this injection directly implies that $|V| \le |W|$ by the standard pigeonhole-type bound for finite types.

  1. There is an injective map $f : V \to W$.

    By definition, $G$ being a subgraph of $H$ (`digraph_is_subgraph_of`) means there is an injective function $f : V \to W$ that preserves edges. We extract this map $f$ and its injectivity hypothesis ($hf$), discarding the edge-preservation property since it is not needed.

    line 3

      rcases h with ⟨f, hf, -⟩
  2. $|V| \le |W|$

    An injective map between finite sets implies that the cardinality of the domain is at most the cardinality of the codomain (`Fintype.card_le_of_injective`).

    line 4

    uses Fintype.card_le_of_injective

      exact Fintype.card_le_of_injective f hf
Fintype.card_le_of_injective
If there exists an injective map between two finite types, then the cardinality of the domain is at most the cardinality of the codomain.

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

/-- If G is a subgraph of H, then the number of vertices of G is at most that of H. -/theorem digraph_subgraph_fintype_card_le {V W : Type*} [Fintype V] [Fintype W] {G : Digraph V} {H : Digraph W} (h : digraph_is_subgraph_of G H) : Fintype.card V ≤ Fintype.card W := by  rcases h with ⟨f, hf, -⟩  exact Fintype.card_le_of_injective f hf
See it in the graphDiscuss this resultChallenge it