Let $a$, $b$ be two different edges in the complete graph $K_n$. Try to find the number of edge cut sets that simultaneously contain $a$ and $b$.
Here, an edge cut of a connected graph $G$ is a set $S$ of $G$'s edges such that $G-S$ is disconnected and $G-S'$ is connected for any proper subset $S'$ of $S$.
I try to calculate based on whether $a$, $b$ have a common vertex, but I don't know the exact answer.
On
I see that there are $2$ edge cut sets and they are either cutting all the edges adjacent to $a$ or all those adjacent to $b$ (each has $n-1$ edges)
Any other edge cutting that will disconnect $a$ and $b$ has more than $n-1$ edges.
On
I'm unsure whether the question asks for the number of smallest edge sets that are an edge cut set and contain both a and b (which can be either 1 or 0, depending whether a and b share a vertex or not), or the number of smallest edge sets amongst all the sets containing a and b, which also happen to be an edge cut set.
We get an edge cut whenever we partition the vertices of $K_n$ into two parts, and take all the edges going between the parts.
Let's consider two cases. First, suppose that edges $a$ and $b$ share an endpoint: they are edges $uv$ and $uw$ for some vertices $u,v,w$. Then we need to put $u$ on one side of the cut and $v,w$ on the other. There are $n-3$ other vertices in $K_n$; each of them can go on $u$'s side of the cut, or on $v$'s side. So there are $2^{n-3}$ possible cuts.
Second, suppose that edges $a$ and $b$ share no endpoints: they are edges $uv$ and $wx$ for some vertices $u,v,w,x$. There are two ways for both edges to be included in the cut: we could put $u,w$ on one side and $v,x$ on the other, or we could put $u,x$ on one side and $v,w$ on the other. Either way we do it, there are $n-4$ other vertices, each of which can go on one of two possible sides. So there are $2^{n-4}$ possible cuts either way, and again there are $2^{n-3}$ possible cuts altogether.