AFTD Auto-Formalizing Theoretical Domains

oriented_diameter_bound_holds_mono

theoremverified

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'.

  1. 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).

    line 3

      intro n G hc hb hd
  2. There 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).

    line 4

      obtain ⟨D, hD, hr⟩ := h n G hc hb hd
  3. The 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'.

    line 5

    uses digraph_reach_within_mono

      exact ⟨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

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)⟩
See it in the graphDiscuss this resultChallenge it