Lower bounds for sensitivity of graph properties
  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. 
Ilan Karpas
cs.CC math.CO