Induced subgraphs of hypercubes anda proof of the Sensitivity ConjectureHao Huang ∗AbstractIn this paper, we show that every p2n�1 � 1q-vertex induced subgraph of the n-
dimensional cube graph has maximum degree at least?
n. This result is best possible,and improves a logarithmic lower bound shown by Chung, Füredi, Graham and Sey-mour in 1988. As a direct consequence, we prove that the sensitivity and degree of aboolean function are polynomially related, solving an outstanding foundational prob
