Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

My course notes give the following definitions; could someone please verify that the last definition is non-standard? (I've spent all evening googling, and isn't "minimum cut" a concept related to cut sets rather than to edge cuts (all terms as defined below)? For example, see and

A cut set of a graph $G$ induced by a partition of $G$'s vertices into sets $X$ and $Y$ is the set of all edges with one endpoint in $X$ and another endpoint in $Y$.

An edge cut of a connected graph $G$ is a set $S$ of $G$'s edges such that $G$-$S$ is disconected and $G$-$S$' is connected for any proper subset $S$' of $S$.

A minimum cut of a graph $G$ is an edge cut of $G$ with the smallest-possible cardinality (called the edge connectivity of $G$).

share|cite|improve this question
Answering my own question: While cut set and edge cut do not mean the same thing, for a connected graph, the set of smallest possible cut sets and the set of smallest possible edge cuts actually do coincide, so both can be defined the same way and given the same name. While the 3rd definition above is not wrong, it is somewhat nonstandard, since "mimimum cut" is typically used in the context of network flows (eg. the max-flow-min-cut algorithm), where cut sets (which are not necessarily edge cuts) are a point of interest. – Ryan May 8 '13 at 22:29

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.