Important results about/requiring multigraphs

Question

Why are multigraphs important? The wikipedia article on multigraphs mentions several different definitions but does not mention key results about multigraphs. So my question can have several levels of answers:

1. Are there any interesting/deep results that hold for multigraph?

2. Are multigraphs required for proving some important results? E.g. from my internet searches I got the feeling that they featured in the proof of the 4-color theorem, but I am not entirely certain of this fact.

3. Are multigraphs unavoidable in some contexts? E.g. the dual graph of a planar graph might end up being a multigraph.

4. Are there any books/papers that focus on multigraphs and might answer the above questions?

Answer 1

I don't know of any book that specifically focuses on multigraphs. However, Diestel writes the following in his book:

Somewhat surprisingly, proving a graph theorem more generally for multigraphs may, on occasion, simplify the proof. Moreover, there are areas in graph theory (such as plane duality; see Chapters 4.6 and 6.5) where multigraphs arise more naturally than graphs, and where any restriction to the latter would seem artifcial and be technically complicated.

(I confess I haven't searched the book for examples of proofs simplified by using multigraphs.)

One reason to consider multigraphs has to do with matroid theory. Parallel edges and loops have natural analogues in matroids, and in this setting it is often natural to allow these, primarily because there are various matroid operations (most notably, taking duals and minors) under which the class of simple matroids is not closed. Thus, in "matroidal" areas of graph theory (such as plane duality and the theory of graph minors) multigraphs often appear naturally.

As for interesting results about multigraphs, the first one that comes to my mind is the Nash-Williams theorem, which characterizes multigraphs that contain $k$ disjoint spanning trees. The fact that this result works for multigraphs has fun applications for simple graphs as well. For example, we can decide whether a graph contains three spanning trees such that each edge is used by at most two of the trees simply by doubling each edge and checking if the resulting multigraph contains three edge-disjoint spanning trees.

Answer 2

Are there any interesting/deep results that hold for multigraph?

(Bipartite) hypergraphs embedded cellularly on compact surfaces are in a one-to-one correspondence with algebraic curves defined over the algebraic numbers. Furthermore, there is a faithful action of the absolute Galois group over $\mathbb Q$ on the set of hypergraphs (not necessarily bipartite) embedded on compact surfaces. This action restricts to a faithful action on multigraphs.

Many combinatorial properties of multigraphs, such as the degree sequence, are invariant under this action. For more detail, look up dessins d'enfants and Grothendieck's Esquisse d'un Programme.