A VERY SHORT PROOF OF SIDORENKO’S INEQUALITY FOR COUNTS OF HOMOMORPHISMS BETWEEN GRAPHS

Abstract A fundamental extremality result due to Sidorenko [‘A partially ordered set of functionals corresponding to graphs’, Discrete Math. 131 (1–3) (1994), 263–277] states that among all connected graphs G on k vertices, the k -vertex star maximises the number of graph homomorphisms of G into any graph H . We provide a new short proof of this result using only a simple recursive counting argument for trees and Hölder’s inequality.