oriented_diameter_bound_holds_mono
If every connected bridgeless graph of diameter d has a strong orientation of diameter at most k, the same holds for every k' >= k (f(d) <= k implies f(d) <= k').
Statement
theorem oriented_diameter_bound_holds_mono {d k k' : ℕ} (hk : k ≤ k')
(h : oriented_diameter_bound_holds d k) : oriented_diameter_bound_holds d k'- Source
- monotonicity of oriented_diameter_bound_holds (OP-119)
- Verified
- 25 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- oriented_diameter_bound_holdsoriented_diameter_bound_holds d k: every finite connected bridgeless simple graph of diameter d (taken on vertex set Fin n, which loses…
- digraph_reach_within_monoReachability within k steps implies reachability within any k' >= k steps.
- digraph_reach_withindigraph_reach_within D k u v: there is a directed walk of length at most k from u to v in the digraph D (equivalently, the directed…
- 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…
- has_strong_orientation_of_diameter_leThe simple graph G has an orientation D (each edge of G gets exactly one direction, no other arcs) in which every ordered pair of vertices…
The proof, explained
To show that the diameter bound holds for k' whenever it holds for k ≤ k', we consider an arbitrary connected bridgeless graph G of diameter d. The hypothesis guarantees an orientation D of G with diameter at most k. Because reachability within k steps implies reachability within k' steps, D itself witnesses that G has an orientation of diameter at most k'.
Let G be an arbitrary connected, bridgeless graph on n vertices with diameter d.
By definition of oriented_diameter_bound_holds, to establish the bound for k', it suffices to show that any graph satisfying these conditions admits a strong orientation of diameter at most k'. We introduce the vertex count n, the graph G, and the assumptions that G is connected (hc), bridgeless (hb), and has diameter d (hd).
intro n G hc hb hdThere exists an orientation D of G in which every vertex can reach every other vertex within k steps.
Applying the hypothesis h (oriented_diameter_bound_holds d k) to G and its properties hc, hb, and hd yields an orientation D of G (witnessed by hD) such that every vertex u can reach every vertex v within k steps (hr).
obtain ⟨D, hD, hr⟩ := h n G hc hb hdThe orientation D has diameter at most k', completing the proof.
Since k ≤ k', any directed path of length at most k is also of length at most k' by digraph_reach_within_mono. Therefore, D itself serves as the required orientation witnessing that G has an orientation of diameter at most k'.
uses
digraph_reach_within_monoexact ⟨D, hD, fun u v => digraph_reach_within_mono D hk u v (hr u v)⟩
digraph_reach_within_mono- If a vertex u can reach a vertex v in a directed graph D within k steps, and k ≤ k', then u can also reach v within k' steps.
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.
theorem oriented_diameter_bound_holds_mono {d k k' : ℕ} (hk : k ≤ k') (h : oriented_diameter_bound_holds d k) : oriented_diameter_bound_holds d k' := by intro n G hc hb hd obtain ⟨D, hD, hr⟩ := h n G hc hb hd exact ⟨D, hD, fun u v => digraph_reach_within_mono D hk u v (hr u v)⟩