Graph classes which have small edge k-cuts

Question

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.

Answer 1

I think you cannot get much more than your condition, at least with respect to the usual structural parameters you mentioned, but it might be studied in another branch of graph theory I am unaware of.

Consider the class $\mathscr C = \{K_{2,t}: t\in \mathbb{N}\}$, all its graphs are planar and bipartite, it has bounded pathwidth, treedepth, is degenerate, and only has very few minors. Yet for $k=2$, your property does not hold as you have a max flow of $t$ between the two vertices of the small part. The only property this class doesn't have is that it has $2$ vertices with unbounded degrees, instead of $1$ in your condition.

The similar but more meaningful notions of wideness asks whether for every $k$ there exists some $k$ vertices (in a suitably large graph $G$ of the class) such that removing some $f(k)$ vertices from $G$ disconnects them. There are several variations, for example if you want them to be $r$-far instead of disconnected, if they can be found in any large enough subgraph of $G$ (with distances in all of $G$), or if $f(k)$ can depend on $|G|$ as well; you can look up almost/uniform/quasi-wide classes. This notion is related to first order logic and to structural properties of graph classes, including nowhere denseness (nowhere dense classes include those of bounded pathwidth, treewidth, excluding a minor, bounded expansion, etc...).