If is a clutter, then the blocker of , denoted , is the clutter with vertex set and edge set consisting of all minimal sets so that for every . Lehman showed that , so blockers give us a type of duality. We define to be the size of the largest collection of disjoint edges in and to be the size of the smallest edge in . It is easy to see that .
1. If is a simple loopless graph, then is a clutter and is the collection of all minimal dominating sets. Here is the size of the largest matching and is the size of the smallest dominating set.
2. Let be a graph and let . Define by setting and letting be the collection of all edge-sets of - paths. Then is a clutter, and is the collection of all minimal edge cuts which separate and . In this case is the maximum number of edge-disjoint - paths, and is the size of the smallest edge-cut separating and , so Menger's theorem (edge-connectivity version) asserts that .
3. Let be a connected graph and let be the clutter on consiting of all edge sets of spanning trees of . Then is the collection of all minimal edge cuts in .
There is a minor relation on clutters which is similar to that on graphs. If is a clutter and , then we may delete to get the clutter with vertex set and edge set consisting of all which do not contain . We contract to get the clutter . These two operations commute, and if is another clutter, we say that is a minor of if a clutter isomorphic to may be obtained from by a sequence of deletions and contractions.