let be a connected undirected graph. assume that are subsets of such that , the partitioning into groups by removing edges or vertices that connect them is called a cut in , and if applied becomes a disconnected graph.
note that although we state that a cut partitions a graph into two groups , the subgraphs restricted to dont necessarily have to be connected, so a cut may result in more than two disconnected subgraphs, for otherwise we call it a simple cut (see fig-cut-1).
for a graph and a set of vertices of , we define to be the set of edges having one endpoint in and one endpoint not in . we say a set of edges of is a cut of if it has the form .
we define to be the set of arcs whose tails are in and whose heads are not in . note that is a subset of . a set of arcs of is a directed cut (a.k.a dicut) if it has the form .
the cut set of a cut in a graph is the set of edges whose endpoints each exist in a different subset of the vertices that would result from the cut: where are the vertex subsets after the cut
for a set of vertices of , we define to be the set of darts whose tails are in and whose heads are not in . note that has one dart for each edge in . we refer to as the dart boundary of in .
let be a graph, let be a connected component of , and let be a subset of the vertices of . we say a cut or a dart cut is a simple cut if is connected in and is connected in . (some authors have used the term bond for this concept.) note that a cut in is minimal among nonempty cuts iff it is a simple cut. any cut can be written as a disjoint union of simple cuts.
let be a graph, and let be a spanning forest of . for a tree edge , let be the connected component of that contains . for , let we call the fundamental cut of in with respect to .
let be a connected planar embedded graph with spanning tree and let be an edge of . then the darts of the fundamental cut of in with respect to are the same as the darts of the fundamental cycle of in with respect to .
the drawing in fig-fund-cut-cycle-duality demonstrates this idea concretely which may help intuition.
