A very short proof of Sidorenko's inequality for counts of homomorphism between graphs

Abstract

We provide a very elementary proof of a classical extremality result due to Sidorenko (Discrete Math. 131.1-3, 1994), which 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$.

v2: A slight variation of the proof has been added as well as slightly more exposition