Written on the Wall II - Conjecture 160

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

Definitions

For a vertex $v$ in $G$, $T(v)$ is the number of triangles incident to $v$: $$T(v) = |\{\{u, w\} \subseteq N(v) \mid u \sim w\}|$$ i.e., the number of pairs of neighbors of $v$ that are themselves adjacent.

The invariant maxTrianglesAtVertex G is the maximum of $T(v)$ over all vertices.

Conjecture 160 uses both $\max_v T(v)$ and $c_{C_4}(G)$ (the number of induced 4-cycles) to lower bound the WOWII invariant $L_s(G)$, the maximum number of leaves over all spanning trees of $G$ (exposed as SimpleGraph.Ls G : ℝ).

noncomputable def WrittenOnTheWallII.GraphConjecture160.maxTrianglesAtVertex {α : Type u_1} [Fintype α] [DecidableEq α] [Nontrivial α] (G : SimpleGraph α) [DecidableRel G.Adj] : ℕ

The maximum number of triangles incident to any vertex in $G$.

Equations

• WrittenOnTheWallII.GraphConjecture160.maxTrianglesAtVertex G = (Finset.image G.numTrianglesAtVertex Finset.univ).max' ⋯

theorem WrittenOnTheWallII.GraphConjecture160.conjecture160 {α : Type u_1} [Fintype α] [DecidableEq α] [Nontrivial α] (G : SimpleGraph α) [DecidableRel G.Adj] (h : G.Connected) : have maxL := (Finset.image G.indepNeighborsCard Finset.univ).max' ⋯; have maxT := maxTrianglesAtVertex G; have cC4 := G.countInducedC4; ↑maxL + ↑maxT * ↑cC4 ≤ G.Ls

WOWII Conjecture 160

For a simple connected graph $G$, $L_s(G) \ge \max_v l(v) + \max_v T(v) \cdot c_{C_4}(G)$ where:

• $L_s(G) = \mathrm{SimpleGraph.Ls}\, G$ is the maximum number of leaves over all spanning trees of $G$,
• $\max_v l(v)$ is the maximum local independence number over vertices,
• $\max_v T(v)$ is the maximum number of triangles incident to any vertex,
• $c_{C_4}(G)$ is the number of induced 4-cycles in $G$.