nLab graph minor

Redirected from "graph minors".
Contents

Contents

Idea

Let GG and HH be simple graphs. Then HH is a graph minor of GG if it is isomorphic to a graph obtained by applying a sequence of operations of the following sort, starting from GG:

  • Removing edges;

  • Removing isolated points;

  • Contracting edges, where contracting an edge means removing it and identifying its endpoints.

Graph minors can be viewed as certain types of subquotients in an appropriate category of graphs; this article describes which subquotients those are in categorical language.

Disclaimer

To be honest, it’s not really clear how a categorical POV (or at least the POV presented here) can usefully inform or guide or clarify graph theory. For the time being, we are just collecting some notes. No deep theorems of graph theory are proved here. The main observation is simply that graphs form a category with very good properties, and there may be potential of putting those properties to effective use some day.

Categorical POV

We take the point of view that a simple graph (consisting of a set of vertices VV and a collection of two-element subsets of VV called “edges”) carries the same information as a set VV equipped with a reflexive symmetric relation EE, and that a morphism of simple graphs should be defined as a function between the vertex-sets which respects such relations. Indeed, such a relation determines and is uniquely determined by a simple graph GG where for given vertices x,yVx, y \in V, there is an edge {x,y}\{x, y\} between xx and yy in GG iff both (x,y)E(x, y) \in E and xyx \neq y. We will write E(x,y)E(x, y) to mean (x,y)E(x, y) \in E.

Remark

Since edges are 22-element subsets, it might seem more natural to interpret a simple graph as a set VV equipped with a symmetric irreflexive relation EE, whereby E(x,x)E(x, x) is false for all xVx \in V. But the result is a rather poor category which lacks certain morphisms we would like, such as edge contractions, at least if we take the morphisms (V,E)(W,F)(V, E) \to (W, F) to be functions f:VWf: V \to W which preserve those relations. Indeed, we could never have both E(x,y)E(x, y) and f(x)=f(y)f(x) = f(y) since irreflexivity of FF would render F(f(x),f(y))F(f(x), f(y)) false. Thus, requiring reflexivity is the more flexible option.

Notice that contraction of edges yields a quotient in this category. For example, if we want to contract a collection of edges by identifying certain points along an equivalence relation RR, that is via some quotient map q:VV/Rq: V \to V/R, then we simply take the image of the composite

EV×Vq×qV/R×V/R;E \hookrightarrow V \times V \stackrel{q \times q}{\to} V/R \times V/R;

notice this image is a reflexive symmetric relation on V/RV/R.

Thus, we let SimpGphSimpGph denote the category of sets equipped with a reflexive symmetric relation. This category is convenient in many respects (for details see category of simple graphs):

Theorem

The category SimpGphSimpGph has the following properties.

  • It is a Grothendieck quasitopos. In particular, both it and its opposite SimpGph opSimpGph^{op} are regular categories.

  • It is an \infty-extensive category.

  • The forgetful functor Γ=hom(1,):SimpGphSet\Gamma = \hom(1, -): SimpGph \to Set is faithful and exhibits SimpGphSimpGph as a topological concrete category.

  • SimpGphSimpGph is cohesive: the adjoint string ΔΓ:SetSimpGph\Delta \dashv \Gamma \dashv \nabla: Set \to SimpGph has a further left adjoint ΠΔ\Pi \dashv \Delta, and Π:SimpGphSet\Pi: SimpGph \to Set preserves products.

Of course Δ\Delta assigns to a set XX the discrete graph on XX (the minimal reflexive relation δ XX×X\delta_X \hookrightarrow X \times X), and \nabla the codiscrete graph (the maximal relation 1 X×X1_{X \times X}), while Π(G)\Pi(G) is the set of connected components of GG. Let γ:1ΔΠ\gamma: 1 \to \Delta \Pi denote the unit of ΠΔ\Pi \dashv \Delta; the component γG:GΔΠ(G)\gamma G: G \to \Delta \Pi (G) takes a vertex vGv \in G to the connected component to which it belongs. Notice that γG\gamma G is a regular epi.

Definition

A contraction map between simple graphs is a morphism π:GG\pi: G \to G' that arises by pushing out a map of the form γK\gamma K along some map f:KGf: K \to G:

K f G γK po π Π(K) G\array{ K & \stackrel{f}{\to} & G \\ \mathllap{\gamma K} \downarrow & po & \downarrow \mathrlap{\pi} \\ \Pi(K) & \to & G' }

is a pushout square. If GGG \to G' is a contraction map, we also say GG' is a contraction of GG.

It is immediate that a contraction map is a regular epi, since every γK\gamma K is regular epi.

Proposition

Contraction maps are closed under composition.

Proof
Definition

A graph HH is a minor of a graph GG if it arises as a subobject of some contraction of GG:

G contraction H G\array{ & & G \\ & & \downarrow \mathrlap{contraction} \\ H & \rightarrowtail & G' }
Proposition

The subquotient relation is reflexive and transitive.

Proof

Reflexivity is clear. For transitivity, we compose subquotients by taking a pushout square as follows.

G G G mono mono H H mono J\array{ G & \twoheadrightarrow & G' & \twoheadrightarrow & G'' \\ & & ^\mathllap{mono} \uparrow & & \uparrow^\mathrlap{mono} \\ & & H & \twoheadrightarrow & H' \\ & & & & \uparrow^\mathrlap{mono} \\ & & & & J }

where we use the simple fact that the pushout of a mono along an arrow in SimpGphSimpGph is a mono (because VertVert reflects monos and preserves monos and pushouts, plus the fact that the pushout of a mono in SetSet is a mono).

For finite graphs, the subquotient relation is also antisymmetric (if GG and HH are minors of one another, then they are isomorphic). Indeed, if either the arrow GGG \twoheadrightarrow G' or the arrow HGH \hookrightarrow G' is not an isomorphism, then HH has strictly fewer edges and vertices than GG. This is clearly not the case for infinite graphs (e.g., the infinite rooted binary tree without leaves contains as a subgraph a disjoint sum of two copies of itself).

(To be expanded, eventually. Hopefully one can develop a categorical story about graph minors in particular.)

Minor-closed families

  • The collection of forests is closed under the graph minor relation.

  • The collection of planar graphs is closed under the graph minor relation.

Graph minor theorem

This celebrated result of Robertson and Seymour says that no collection of finite graphs, ordered by the graph minor relation, has an infinite antichain. Equivalently, that in any collection of finite graphs, there are only finitely many elements which are minimal with respect to the graph minor relation.

As a corollary, any class FF of finite graphs which is closed under minors admits a forbidden minor characterization: is precisely the class of graphs which do not have any members of a specific finite family of graphs as a minor. (Proof: the complement of FF in the poset of finite graphs has finitely many minimal members. Then, xx belongs to FF iff none of these minimal members occurs as a minor of xx.

For example, the class of forests is precisely the class of finite graphs which do not have a triangle K 3K_3 as a minor. The class of planar graphs is precisely the class of finite graphs which do not have K 5K_5 or K 3,3K_{3, 3} as a minor.

Forbidden minor characterizations also exist for certain classes of matroids. (See for example Wikipedia here.)

References

  • Wikipedia article on graph minors (link)

Last revised on July 31, 2023 at 17:32:53. See the history of this page for a list of all contributions to it.