digraph_has_isolated_edge_card_ge_two
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.
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).
obtain ⟨u, v, huv, -⟩ := hu ≠ 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.
have hne : u ≠ v := by intro heq subst v exact (hG u u huv) huv
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.
uses
Fintype.one_lt_card_iffhave hlt : 1 < Fintype.card V := (Fintype.one_lt_card_iff).2 ⟨u, v, hne⟩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.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- 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