I am interested in graph classes that have the following property: There exists a function $f(k)$ such that for every graph $G$ in the class, for every choice of $k$ vertices $v_1, \ldots, v_k$ in the graph, there exists an edge cut of cardinality at most $f(k)$ which separates all the given $k$ vertices. That is, there exists a set of at most $f(k)$ edges whose removal disconnects $v_i$ from $v_j$ for all $i \neq j$. I don't need this for anything bigger than constant $k$ - even just having it for $k = 3$ wouldn't be entirely uninteresting.

A very simple example of such a class would be the graphs with maximum degree $\Delta$ - just removing all the edges incident to $k-1$ of the given vertices gets us a cut of size at most $(k-1)\Delta$. (Of course, as the same proof holds, the same holds for graphs where all vertices except possibly one have degree at most $\Delta$ - so the bounded maximum degree is not the best possible result.)

A bit of thinking about this while doing the dishes led me to believe that there should probably be some way to relate this to the existence of certain minors, and perhaps also to one of the many width parameters that have been defined for a graph. (Treewidth, pathwidth, et.c., et.c.) However, a bit of Googling and thinking about it didn't yield a precise statement, but it seems like the kind of thing that should be known/easy to people more comfortable with these notions - thus asking here, before spending more hours on figuring it out myself.

I am interested in graph classes that have the following property: There exists a function $f(k)$ such that for every graph $G$ in the class, for every choice of $k$ vertices $v_1, \ldots, v_k$ in the graph, there exists an edge cut of cardinality at most $f(k)$ which separates all the given $k$ vertices. That is, there exists a set of at most $f(k)$ edges whose removal disconnects $v_i$ from $v_j$ for all $i \neq j$. I don't need this for anything bigger than constant $k$ - even just having it for $k = 3$ wouldn't be entirely uninteresting.

A very simple example of such a class would be the graphs with maximum degree $\Delta$ - just removing all the edges incident to $k-1$ of the given vertices gets us a cut of size at most $(k-1)\Delta$. (Of course, as the same proof shows, the same holds for graphs where all vertices except possibly one have degree at most $\Delta$ - so the bounded maximum degree is not the best possible result.)

A bit of thinking about this while doing the dishes led me to believe that there should probably be some way to relate this to the existence of certain minors, and perhaps also to one of the many width parameters that have been defined for a graph. (Treewidth, pathwidth, et.c., et.c.) However, a bit of Googling and thinking about it didn't yield a precise statement, but it seems like the kind of thing that should be known/easy to people more comfortable with these notions - thus asking here, before spending more hours on figuring it out myself.