AUTOMATED CONJECTURING VII: THE GRAPH BRAIN PROJECT & BIG MATHEMATICS

NEW

Problem: Reconstructed statement: for every finite simple graph $G$,

where $\alpha$ is independence number, $\vartheta$ is the usual Lovász theta number satisfying $\alpha(G)\le \vartheta(G)$, and $g(G)$ is girth. The conjecture text lists exactly these graph invariants. The counterexample below is connected and has a triangle, so it is unaffected by common connectedness or girth-convention ambiguities.

Result: The statement is false.

Let $H$ be the disjoint union of $13$ copies of $C_5$, and let

be the join of $H$ with one new universal vertex.

Standard theta facts: $\vartheta(C_5)=\sqrt5$, $\vartheta$ is additive on disjoint unions, and

Hence

Since $29^2<13^2\cdot 5<30^2$, we have

Also, each $C_5$ has independence number $2$, so

The universal vertex cannot be used together with any vertex of $H$, hence

Finally, $G$ contains a triangle: the universal vertex together with any edge of a $C_5$. Thus

Therefore the conjectured inequality gives

which is false. So this connected $66$-vertex graph is a counterexample.

Citation: The theta facts used above are classical; see L. Lovász, “On the Shannon capacity of a graph,” IEEE Trans. Inform. Theory 25 (1979), 1–7.