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.
Best Answer
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.