Written on the Wall II - Conjecture 36

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

noncomputable def WrittenOnTheWallII.GraphConjecture36.dp {α : Type u_1} [Fintype α] (G : SimpleGraph α) : ℕ

dp G is the number of diametrical pairs of G: the number of unordered pairs {u, v} of vertices at distance diam(G).

Equations

• WrittenOnTheWallII.GraphConjecture36.dp G = {p : Sym2 α | Sym2.lift ⟨fun (u v : α) => G.dist u v = G.diam ∧ u ≠ v, ⋯⟩ p}.card

theorem WrittenOnTheWallII.GraphConjecture36.conjecture36 : False ↔ ∀ {α : Type u_1} [inst : Fintype α] [inst_1 : DecidableEq α] [Nontrivial α] (G : SimpleGraph α) [DecidableRel G.Adj], G.Connected → 0 < dp G → 2 * ↑G.radius.toNat / ↑(dp G) ≤ ↑G.path

WOWII Conjecture 36:

For every finite simple connected graph $G$, $\operatorname{path}(G) \ge 2 \cdot \operatorname{rad}(G) / \operatorname{dp}(G)$, where $\operatorname{path}(G)$ is the floor of the average distance of $G$, $\operatorname{rad}(G)$ is the radius of $G$, and $\operatorname{dp}(G)$ is the number of diametrical pairs of $G$ — that is, the number of pairs of vertices at distance $\operatorname{diam}(G)$.

Disproved by Waller in Oct 2003 (counterexample: path number 5, radius 3, dp 1).