Definition in the textbook
definition-edge cut is the set of edges which disconnect the graph if we remove it from the edge set of the graph.
How are these two definitions equivalent?
2026-04-01 18:54:38.1775069678
On
How are these two definitions equivalent?
72 Views Asked by Bumbble Comm https://math.techqa.club/user/bumbble-comm/detail At
2
There are 2 best solutions below
4
On
They are not completely equivalent -- for example, consider
5
/ \
1---2---3---4
The set $\{23\}$ is an edge cut according to both definitions (take $S=\{1,2\}$, for example).
The second definition appears to allow $\{23,34\}$ to be an edge cut: removing those edges certainly disconnects the graph. I don't think it is standard to consider $\{23,34\}$ a cut, however -- the definition should be that it is a minimal set of edges whose removal will disconnect the graph.
The first definition defines that if you can divide your graph into two disjoint sets of vertexes. And the edge-cut as the set of edges that connect these two sets of vertexes.
The second definition defines and edge cut as a set of edges that would disconnect these two sets of vertexes.