Written on the Wall II - Conjecture 101

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

Definitions

The $\alpha$-core of a graph $G$, written alphaCore G, is the set of vertices $v$ such that removing $v$ strictly decreases the independence number: $$\mathrm{alphaCore}(G) = \{v \mid \alpha(G - v) < \alpha(G)\}$$ where $G - v$ is the subgraph of $G$ induced on $V(G) \setminus \{v\}$.

These vertices are also called "critical vertices for independence."

noncomputable def WrittenOnTheWallII.GraphConjecture101.indepNumDeleteVertex {α : Type u_1} (G : SimpleGraph α) (v : α) : ℕ

The independence number of the subgraph induced on $V \setminus \{v\}$ (i.e., the graph $G - v$).

Equations

• WrittenOnTheWallII.GraphConjecture101.indepNumDeleteVertex G v = (SimpleGraph.induce (Set.univ \ {v}) G).indepNum

noncomputable def WrittenOnTheWallII.GraphConjecture101.alphaCore {α : Type u_1} [Fintype α] (G : SimpleGraph α) : Finset α

The $\alpha$-core of $G$: the set of vertices whose removal strictly decreases the independence number. A vertex $v$ is in the $\alpha$-core if $\alpha(G - v) < \alpha(G)$.

Equations

• WrittenOnTheWallII.GraphConjecture101.alphaCore G = {v : α | WrittenOnTheWallII.GraphConjecture101.indepNumDeleteVertex G v < G.indepNum}

theorem WrittenOnTheWallII.GraphConjecture101.conjecture101 {α : Type u_1} [Fintype α] [DecidableEq α] [Nontrivial α] (G : SimpleGraph α) [DecidableRel G.Adj] (h : G.Connected) : G.indepNum ≤ (Fintype.card α + (alphaCore G).card) / 2

WOWII Conjecture 101

For a simple connected graph $G$, $\alpha(G) \le \lfloor (n + |\mathrm{alphaCore}(G)|) / 2 \rfloor$ where $\alpha(G) = G.\mathrm{indepNum}$ is the independence number, $n$ is the number of vertices, and $\mathrm{alphaCore}(G)$ is the set of vertices whose removal decreases the independence number.

This is a theorem known to follow from inclusion-exclusion principles.