exists_principal_vertex_of_is_perron_vector
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.
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.
uses
Finite.exists_maxobtain ⟨u, hu⟩ := Finite.exists_max vecThe 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.
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
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.
/-- 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⟩