Eulerian finite simple graph
DefinitionNondetConn_Supplement_isEuleriancommunication-complexityeulerian-graphsgraph-propertiesp2o-gran-per-chapterp2o-plan-paperp2o-v1
A finite simple graph is Eulerian when it is connected and every vertex has even degree.
This is exactly the characterization used in the proof of Theorem 6.2, where every vertex of the reduction graph has degree two.
Definition code
import Mathlib
set_option autoImplicit false
namespace NondetConn.Supplement
/-- A finite simple graph is Eulerian when it is connected and every vertex has even
degree, the convention used in the proof of Zhang's Theorem 6.2. -/
noncomputable def isEulerian {V : Type} [Fintype V] (G : SimpleGraph V) : Prop := by
classical
exact G.Connected ∧ ∀ v, Even (G.degree v)
end NondetConn.Supplement
Source
Zhang, Settling Nondeterministic Communication Complexity of Graph Connectivity, arXiv:2610.32346 (held version, sha256 1d4f00d1…4e7ac), proof of Theorem 6.2, p.26 (PDF p.28)