I'm learning Graph Theory from Introduction to Graph Theory by Robin J. Wilson.

In chapter 3 he defines disconecting set and gives an example as follows:

See definition and example.

Then, he defines cutset in terms of desconecting set, like this:

See definition here.

*When he says "in the above example" he refers to the example in the first image.

After defining cutset, he states that $ \{ e_3, e_6, e_7, e_8 \} $ is a cutset of the exemplifying graph; nonehtheless, $ \{ e_3, e_4, e_6, e_7, e_8 \} $ is also a disconnecting set, and $ \{ e_3, e_6, e_7, e_8 \} ⊂ \{ e_3, e_4, e_6, e_7, e_8 \} $, so, according to the definition of cutset $ \{ e_3, e_6, e_7, e_8 \} $ can't be one, contradictory.

I'm sure there's something I'm not getting from that definition ¿Could you provide me with a better defition of cutset than the one in the book, or explain to me what I seem not to be getting?

Thanks in advance.

  • $\begingroup$ A cutset is a minimal disconnecting set. It is not supposed to have any disconnecting subsets, so $\{e_3,e_6,e_7,e_8\}$ is ok. $\endgroup$ Nov 19, 2019 at 23:03

1 Answer 1


The definition seems to say that a cut set is a minimal disconnecting set, so the existence of a larger disconnecting set doesn't appear to be a problem.

  • $\begingroup$ Oh, ok... English isn't my native language, so the phrasing of the definition of cutset seems to be confusing me... ¿could someone be so kind and write it in a more simple manner, specially without using that "of which"? $\endgroup$ Nov 19, 2019 at 23:07
  • $\begingroup$ I'd just say "a cut set is a minimal disconnecting set." $\endgroup$ Nov 19, 2019 at 23:08

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .