A graph $G$ is {\em balanced\/} if the maximum ratio of edges to vertices,
taken over all subgraphs of $G$, occurs at $G$ itself. This note uses the
max-flow/min-cut theorem to prove a good characterization of balanced graphs.
This characterization is then applied to some results on how balanced graphs
may be combined to form a larger balanced graph. In particular, we show that
edge-transitive graphs and complete $m$-partite graphs are balanced, that a
product or lexicographic product of balanced graphs is balanced, and that the
normal product of a balanced graph and a regular graph is balanced.
DIMACS Home Page