Lower bounds for sensitivity of graph properties

Ilan Karpas

We prove that the sensitivity of any non-trivial graph property on $n$ vertices is at least $\lfloor \frac{1}{2}n\rfloor$ , provided $n$ is sufficiently large.