The five graph properties of Theorem 6.2
DefinitionNondetConn_Supplement_GraphPropertycommunication-complexitygraph-propertieslower-boundsp2o-gran-per-chapterp2o-plan-paperp2o-v1
Theorem 6.2 treats five graph-decision properties in one result: bipartite, cycle-free, Eulerian, Hamiltonian, and planar.
This finite type indexes those five clauses without dropping or splitting any of them.
Definition code
import Mathlib set_option autoImplicit false namespace NondetConn.Supplement /-- The five graph properties in Zhang's Theorem 6.2. -/ inductive GraphProperty where | bipartite | cycleFree | eulerian | hamiltonian | planar deriving DecidableEq end NondetConn.Supplement
Source
Zhang, Settling Nondeterministic Communication Complexity of Graph Connectivity, arXiv:2610.32346 (held version, sha256 1d4f00d1…4e7ac), Theorem 6.2, p.21 (PDF p.23)