The vertex Folkman number $F_v(3,3;5)$ equals~$8$

Abstract

The vertex Folkman number $F_v(s,t;k)$ is the smallest $n$ for which there exists a $K_k$-free graph on $n$ vertices whose vertices cannot be $2$-colored without producing a monochromatic copy of $K_s$ or $K_t$. We show $F_v(3,3;5)=8$. The witness is the cone $K_1\vee \overline{C_7}$, a single universal vertex joined to the complement of a $7$-cycle. That this graph is $K_5$-free and arrows $(3,3{)}^v$ follows from a short independence-number argument. The matching lower bound -- no $K_5$-free graph on $7$ or fewer vertices works -- comes from exhaustive enumeration via nauty and a SAT check using Glucose\,4. The appendix has a self-contained Python script for verification.

arXiv commentWithdrawn: this result is not new. The value F_v(3,3;5)=8 with witness K_1 + complement(C_7) is established in T. Luczak, A. Rucinski, S. Urbanski, On minimal Folkman graphs, Discrete Mathematics 236 (2001) 245-262, Theorem 2 (p. 250). I missed this reference during the prior-work search before posting v1. Apologies for the duplication.