Written on the Wall II - Conjecture 198a

Reference: E. DeLaVina, Written on the Wall II, Conjectures of Graffiti.pc

theorem WrittenOnTheWallII.GraphConjecture198a.conjecture198a {α : Type u_1} [Fintype α] [DecidableEq α] [Nontrivial α] (G : SimpleGraph α) (h : G.Connected) (hb : G.b ≤ 2 + G.averageEccentricity) : ∃ (a : α) (b : α) (p : G.Walk a b), p.IsHamiltonian

WOWII Conjecture 198a

For a simple connected graph G, if b(G) ≤ 2 + ecc_avg(G), then G has a Hamiltonian path. Here b(G) is the number of vertices in a largest induced bipartite subgraph, and ecc_avg(G) is the average eccentricity of G. A Hamiltonian path is a walk visiting every vertex exactly once.