AFTD Auto-Formalizing Theoretical Domains

digraph_has_isolated_edge_card_ge_two

theoremverified

If a finite oriented digraph G : Digraph V satisfies digraph_has_isolated_edge G and digraph_is_oriented G, then Fintype.card V ≥ 2.

Statement

theorem digraph_has_isolated_edge_card_ge_two {V : Type*} [Fintype V] {G : Digraph V} (hG : digraph_is_oriented G) (h : digraph_has_isolated_edge G) : 2 ≤ Fintype.card V
Source
folklore
Verified
24 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • digraph_is_orientedA digraph G : Digraph V on vertex type V is oriented (digraph_is_oriented G) if for all vertices u v : V, G.Adj u v implies ¬ G.Adj v u.
  • digraph_has_isolated_edgeA digraph G on vertex type V has an isolated edge if there exist vertices u and v such that G has a directed edge from u to v, and every…

Read back from the Lean

For any finite type V and any directed graph G on V, if G is oriented (for all u, v : V, if u is adjacent to v, then v is not adjacent to u) and G has an isolated edge (there exist vertices u, v : V such that u is adjacent to v, and for all w : V, if w is adjacent to or from u or v, then w = u or w = v), then the cardinality of V is at least 2.

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

The proof extracts an edge from u to v from the assumption that G has an isolated edge. Because G is oriented, it cannot contain self-loops, which forces u ≠ v. Having at least two distinct vertices means the cardinality of V is strictly greater than 1, and hence at least 2 by integer arithmetic.

  1. There exist vertices u and v with an edge from u to v.

    By definition, an isolated edge in G provides two vertices u and v such that G has a directed edge from u to v (and no other edges connect to them, though the remaining conditions are discarded).

    line 3

      obtain ⟨u, v, huv, -⟩ := h
  2. u ≠ v

    Assume for contradiction that u = v. Then the edge is a self-loop from u to u. However, since G is oriented (hG), an edge from u to u implies there is no edge from u to u, a contradiction.

    lines 4–7

      have hne : u ≠ v := by
        intro heq
        subst v
        exact (hG u u huv) huv
  3. 1 < Fintype.card V

    Since u and v are two distinct vertices in V, Fintype.one_lt_card_iff shows that the cardinality of V is strictly greater than 1.

    line 8

    uses Fintype.one_lt_card_iff

      have hlt : 1 < Fintype.card V := (Fintype.one_lt_card_iff).2 ⟨u, v, hne⟩
  4. 2 ≤ Fintype.card V

    Since the cardinality of V is a natural number strictly greater than 1, linear integer arithmetic (omega) closes the goal 2 ≤ Fintype.card V.

    line 9

      omega
Fintype.one_lt_card_iff
A finite type has cardinality strictly greater than 1 if and only if it contains two distinct elements.

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

/-- An oriented graph with an isolated edge has at least two vertices. -/theorem digraph_has_isolated_edge_card_ge_two {V : Type*} [Fintype V] {G : Digraph V} (hG : digraph_is_oriented G) (h : digraph_has_isolated_edge G) : 2 ≤ Fintype.card V := by  obtain ⟨u, v, huv, -⟩ := h  have hne : u ≠ v := by    intro heq    subst v    exact (hG u u huv) huv  have hlt : 1 < Fintype.card V := (Fintype.one_lt_card_iff).2 ⟨u, v, hne⟩  omega
See it in the graphDiscuss this resultChallenge it