I'm having a bit of trouble finding any references in the literature about optimizing functions defined on the set of graphs, i.e. in particular where the number of vertices is not fixed. For example, consider generalizations of finding a graph of minimum size that maximizes the max flow between two fixed and distinguished vertices subject to various constraints on the edge capacities and vertex degrees.
Thank you for the help!
This is called max flow-min cut problem in graphs that states that max flow from a given source to a sink is equal to minimum cut that will separate the source from the sink. Basically these are kind of dual problem as you'll find in an LP and is proven by Ford-Fulkerson theorem.
References:
Wiki
Princeton