AFTD Auto-Formalizing Theoretical Domains

orientation_out_degree_le_degree

theoremverified

In any orientation D of a finite simple graph G, the out-degree of any vertex v in D is at most the degree of v in G.

Statement

lemma orientation_out_degree_le_degree {V : Type*} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) [DecidableRel G.Adj] (D : Digraph V) [DecidableRel D.Adj]
    (hD : is_graph_orientation G D) (v : V) :
    (Finset.filter (D.Adj v) Finset.univ).card ≤ G.degree v
Source
arXiv:2610.30174, Theorem 2.1
Verified
23 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • is_graph_orientationA digraph D is an orientation of a simple graph G if every edge of G is assigned exactly one direction in D, and non-adjacent pairs in G…
Used by 1
  • additive_coloring_bound_by_degreeLet G = (V, E) be a finite simple graph, and let a : V → ℕ assign a positive integer to each vertex. Then there exists an additive…

Read back from the Lean

For any finite type V with decidable equality, any simple graph G on V with decidable adjacency, any digraph D on V with decidable adjacency, if D is an orientation of G (meaning for all vertices u, v : V, D.Adj u v ∨ D.Adj v u ↔ G.Adj u v and ¬(D.Adj u v ∧ D.Adj v u)), then for every vertex v : V, the out-degree of v in D (the cardinality of the set of vertices w : V such that D.Adj v w) is less than or equal to the degree of v in G.

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 out-degree of a vertex v in D is the cardinality of its out-neighborhood, while its degree in G is the cardinality of its neighbor set. The proof reduces the inequality between their cardinalities to a set inclusion: every out-neighbor of v in D is a neighbor of v in G. This inclusion holds directly from the definition of a graph orientation, which ensures that any directed edge from v to u implies an undirected edge between v and u in G.

  1. It suffices to show that the out-neighborhood of v in D is a subset of the neighbor set of v in G.

    Expanding the definition of the graph degree of v as the cardinality of its neighbor finset via `SimpleGraph.degree`, the inequality asserts that the out-degree of v is at most the size of its neighbor set in G. By monotonicity of cardinality (`Finset.card_le_card`), this inequality reduces to proving the set inclusion: every vertex in the filtered out-neighborhood of v is also in the neighbor finset of v in G.

    lines 6–7

    uses SimpleGraph.degree, Finset.card_le_card

      rw [SimpleGraph.degree]
      apply Finset.card_le_card
  2. Every out-neighbor of v in D is adjacent to v in G, completing the inclusion.

    Let u be any vertex in the out-neighborhood of v. Unfolding membership in the filtered finset using `Finset.mem_filter`, `Finset.mem_univ`, and `true_and`, we obtain that there is a directed edge from v to u in D (that is, `D.Adj v u`). By `SimpleGraph.mem_neighborFinset`, membership of u in G's neighbor finset is equivalent to adjacency `G.Adj v u`. Since D is an orientation of G, having a directed edge in either direction implies adjacency in G (`hD.1`). Providing `D.Adj v u` as the left disjunct via `Or.inl` proves `G.Adj v u`.

    lines 8–11

    uses Finset.mem_filter, Finset.mem_univ, true_and, SimpleGraph.mem_neighborFinset, Or.inl

      intro u hu
      simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hu
      rw [SimpleGraph.mem_neighborFinset]
      exact (hD.1 v u).mp (Or.inl hu)
SimpleGraph.degree
The degree of a vertex in a simple graph is defined as the cardinality of its neighbor finset.
Finset.card_le_card
If one finite set is a subset of another, its cardinality is at most the cardinality of the other set.
Finset.mem_filter
An element belongs to the filtered finset {x ∈ s | p x} if and only if it belongs to s and satisfies the predicate p.
Finset.mem_univ
Every element of a finite type belongs to the universal finset `Finset.univ`.
true_and
The proposition `True ∧ p` simplifies to `p`.
SimpleGraph.mem_neighborFinset
A vertex w is an element of the neighbor finset of v in G if and only if v and w are adjacent in G.
Or.inl
Given a proof of a proposition a, construct a proof of the disjunction a ∨ b.

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

/-- In any orientation of a graph G, the out-degree of each vertex is at most its degree in G. -/lemma orientation_out_degree_le_degree {V : Type*} [Fintype V] [DecidableEq V]    (G : SimpleGraph V) [DecidableRel G.Adj] (D : Digraph V) [DecidableRel D.Adj]    (hD : is_graph_orientation G D) (v : V) :    (Finset.filter (D.Adj v) Finset.univ).card ≤ G.degree v := by  rw [SimpleGraph.degree]  apply Finset.card_le_card  intro u hu  simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hu  rw [SimpleGraph.mem_neighborFinset]  exact (hD.1 v u).mp (Or.inl hu)
See it in the graphDiscuss this resultChallenge it