MathDB
max min in a graph

Source: KoMaL A. 829

June 11, 2022
combinatoricsgraph theory

Problem Statement

Let GG be a simple graph on nn vertices with at least one edge, and let us consider those S:V(G)→R≥0S:V(G)\to\mathbb R^{\ge 0} weighings of the vertices of the graph for which ∑v∈V(G)S(v)=1\sum_{v\in V(G)} S(v)=1. Furthermore define f(G)=max⁡Smin⁡(v,w)∈E(G)S(v)S(w),f(G)=\max_S\min_{(v,w)\in E(G)}S(v)S(w), where SS runs through all possible weighings.
Prove that f(G)=1n2f(G)=\frac1{n^2} if and only if the vertices of GG can be covered with a disjoint union of edges and odd cycles.
(V(G)V(G) denotes the vertices of graph GG, E(G)E(G) denotes the edges of graph GG.)
Back to ProblemsView on AoPS