KöMaL 2022 A829

Let $G$ be a simple graph on $n$ vertices with at least one edge, and let us consider those $S\colon V(G)\to \mathbb{R}^{\ge 0}$ weighings of the vertices of the graph for which $\sum\limits_{v\in V(G)}S(v)=1$. Furthermore define $f(G)=\max_S \min_{(v,w)\in E(G)} S(v)S(w),$ where $S$ runs through all possible weighings. Prove that $f(G)=\frac{1}{n^2}$ if and only if the vertices of $G$ can be covered with a disjoint union of edges and odd cycles. ($V(G)$ denotes the vertices of graph $G$, $E(G)$ denotes the edges of graph $G$.)