AFTD Auto-Formalizing Theoretical Domains

exists_principal_vertex_of_is_perron_vector

theoremverified

In any finite nonempty simple graph G, if there exists a Perron vector vec, then there exists a principal vertex u of G.

Statement

theorem exists_principal_vertex_of_is_perron_vector
    {V : Type*} [Fintype V] [Nonempty V] [DecidableEq V]
    (G : SimpleGraph V) (vec : V → ℝ) (hvec : is_perron_vector G vec) :
    ∃ u : V, is_principal_vertex G u
Source
folklore
Verified
24 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • is_perron_vectorFor a simple graph G on a finite vertex type V, a vector vec : V → ℝ is a Perron vector if every component vec i is strictly positive and…
  • is_principal_vertexFor a simple graph G on a finite vertex type V, a vertex u is a principal vertex if there exists a Perron vector vec of G such that vec v…

Read back from the Lean

For any finite, nonempty type V with decidable equality, any simple graph G on V, and any function vec : V → ℝ, if vec is a Perron vector of G (that is, every entry of vec is strictly positive and vec is an eigenvector of the real adjacency matrix of G with eigenvalue equal to the real-valued spectral radius of the adjacency matrix), then there exists a vertex u : V that is a principal vertex of G (that is, there exists a Perron vector of G whose entries are all less than or equal to its value at u).

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

By definition, a vertex is principal if it maximizes some Perron vector of the graph. Since the vertex set is finite and nonempty, any given Perron vector attains its maximum at some vertex, which is then immediately a principal vertex.

  1. There exists a vertex u that maximizes the Perron vector vec

    Since the vertex set V is finite and nonempty, the real-valued function vec attains a maximum at some vertex u ∈ V, meaning vec x ≤ vec u for all x ∈ V.

    line 6

    uses Finite.exists_max

      obtain ⟨u, hu⟩ := Finite.exists_max vec
  2. The vertex u is a principal vertex of G

    By definition, a vertex is principal if there exists some Perron vector that it maximizes. The vertex u, together with vec, the assumption that vec is a Perron vector, and its maximality at u, directly witnesses this definition.

    line 7

      exact ⟨u, vec, hvec, hu⟩
Finite.exists_max
Any function from a finite, nonempty type to a linearly ordered type attains a maximum value.

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

/-- If a finite nonempty simple graph has a Perron vector, then it has a principal vertex. -/theorem exists_principal_vertex_of_is_perron_vector    {V : Type*} [Fintype V] [Nonempty V] [DecidableEq V]    (G : SimpleGraph V) (vec : V → ℝ) (hvec : is_perron_vector G vec) :    ∃ u : V, is_principal_vertex G u := by  obtain ⟨u, hu⟩ := Finite.exists_max vec  exact ⟨u, vec, hvec, hu⟩
See it in the graphDiscuss this resultChallenge it