orientation_out_degree_le_degree
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.
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.
uses
SimpleGraph.degree,Finset.card_le_cardrw [SimpleGraph.degree] apply Finset.card_le_card
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`.
uses
Finset.mem_filter,Finset.mem_univ,true_and,SimpleGraph.mem_neighborFinset,Or.inlintro 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
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.
/-- 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)