  We present a connection between two seemingly disparate fields: VC-theory and
graph theory. This connection yields natural correspondences between
fundamental concepts in VC-theory, such as shattering and VC-dimension, and
well-studied concepts of graph theory related to connectivity, combinatorial
optimization, forbidden subgraphs, and others.
  In one direction, we use this connection to derive results in graph theory.
Our main tool is a generalization of the Sauer-Shelah Lemma. Using this tool we
obtain a series of inequalities and equalities related to properties of
orientations of a graph. Some of these results appear to be new, for others we
give new and simple proofs.
  In the other direction, we present new illustrative examples of
shattering-extremal systems - a class of set-systems in VC-theory whose
understanding is considered by some authors to be incomplete. These examples
are derived from properties of orientations related to distances and flows in
networks.
