Graph Minor Theory, Part 2


< See Part 1

Recall that a graph is planar if it can be drawn on the plane without edge crossings. In the last post, I mentioned Kuratowski’s characterization of planar graphs:

Kuratowski’s Theorem. A graph is planar if and only if it has neither K_5 nor K_{3,3} as a minor:

Kuratowski’s K_5 and K_3,3

(Here K_5 refers to the complete graph on 5 vertices, and K_{3,3} is the complete bipartite graph on two sets of three vertices.)

I don’t know a really elegant proof of this theorem, but I do have some sense of why these two graphs are the right forbidden minors.

K_{3,3} and the Jordan Curve Theorem

The basic topological property of the plane is the Jordan Curve Theorem — any closed loop separates the plane into two components. This has some interesting consequences for graph drawing.

A Copy of K4

The above graph consists of a single loop with two red edges attached. If we wish to avoid crossings, the red edges must be drawn on opposite sides of the loop. By the Jordan Curve Theorem, it follows that the red edges are in different components of the complement of the loop. In particular, the blue edge in the following graph always crosses the loop:

A Copy of K{3,3}

This graph is exactly K_{3,3}. As you can see, the statement “K_{3,3} is not planar” is a graph-theoretic version of the Jordan Curve Theorem.

The Möbius Strip

One surface for which the Jordan Curve Theorem fails is the Möbius strip. This is the surface obtained by gluing joining two ends of a rectangle with a half-twist:

Möbius Strip

If you cut the Möbius Strip along its center loop, you get a single twisted cylinder:

Cutting a Möbius Strip

(There is a nice video of this on YouTube.) In particular, cutting the Möbius strip along the center loop doesn’t seperate it into two components. This makes it possible to embed K_{3,3} in the Möbius strip without crossings:

K{3,3} on the Möbius Strip

What About K_5?

If K_{3,3} represents the Jordan Curve Theorem, what is the role of the other forbidden minor, K_5?


It turns out that K_5 is somewhat less interesting than K_{3,3}. To understand why, let us examine the proof that K_5 isn’t planar.

Theorem. K_5 is not planar.
Proof: This is a proof by contradiction. Suppose that you could draw K_5 on the plane without crossings, and consider a neighborhood of one of the vertices:

Vertex Neighborhood

We don’t know much about how the graph is drawn, but we do know that there are four edges coming out of this vertex. Consider what happens if we “split” the vertex in two:

Vertex Splitting

This result is new graph drawn on the plane, with one more vertex and one more edge than K_5. This new graph is isomorphic to the middle graph shown below:

Proof that K5 is not planar

The contradiciton is that the new graph contains a copy of K_{3,3}. Since K_{3,3} can’t be drawn without crossings, neither can the splitting, and so neither can K_5. \,\,\,\,\square

As you can see, K_5 is essentially just a tagalong to K_{3,3}. Its failure to be planar doesn’t really convey any new topology.

Before ending this post, I should mention that K_5 can be drawn on the Möbius strip fairly easily. (Try this for yourself.) This leaves us with an important question: is there any graph that can’t be drawn on a Möbius strip?

> Continue to Part 3

8 Responses to “Graph Minor Theory, Part 2”

  1. ComplexZeta Says:

    A Möbius strip satisfies the six-color theorem (reference: Mathworld), so K_7 cannot be drawn on a Möbius strip.

  2. Jim Belk Says:

    That is true, K_7 cannot be drawn on a Möbius strip, and neither can any other graph with chromatic number 7.

    I haven’t talked about graph coloring in any of my posts, but it is known that every surface possesses a “color theorem” analogous to the four color theorem for the plane. For example, graphs on the Möbius strip require up to 6 colors, and graphs on the torus require up to 7 colors. (Click here for the general formula.) This provides a large class of graphs that cannot be drawn on any given surface.

  3. Graph Minor Theory « Abner’s Postgraduate Days Says:

    […] Graph Minor Theory, Part II « The Everything Seminar […]

  4. El problema de las tres casas y los tres suministros y la banda de Möbius - Gaussianos Says:

    […] Graph Minor Theory, Part 2 en The Everything Seminar. […]

  5. Says:

    A person necessarily help to make seriously posts I might state.
    That is the very first time I frequented your web page and up to now?
    I amazed with the research you made to create this particular post
    amazing. Great activity!

  6. Tanisha Says:

    Yes! Finally something about meet people today.

  7. yahoo Says:

    There’s definately a great deal to know about this subject.
    I really like all the points you’ve made.

  8. prof dr mircea orasanu Says:

    here we mention these specifically as precised prof dr mircea orasanu and prof drd horia orasanu that appear necessary and followed , these being important publication ,
    where is a non-decreasing -order-convex function on a partially set and .
    Let be a guaranteed error estimate for the gradient algorithm in some unperturbed (perturbed) discrete optimization problem. As usual (see. [3]), we say that the gradient algorithm is stable if , where as .
    Theorem. Let and be guaranteed error estimates for the gradient algorithm in Problems A and B, respectively. Then .
    To prove Theorem, we need the following lemma.
    Lemma. The gradient maximum and the global maximum of any -ordered-convex non-decreasing function on are connected by the following relations:
    , (1)

    – is the set of all maximal elements of the partially ordered set .
    Proof of Lemma. By virtue of item of Theorem 4 [4], we have for

    Together with the fact that
    the last inequality yields





    Then, by repeating the scheme of the proof of Theorem 4 [4], we obtain estimates (1). Lemma is proved.
    Proof of Theorem. According to Lemma
    , (2) . (3)
    (2), (3) and the relations bottom follow from theorem

    Theorem is proved.
    Corollary. If , then .

    [1] Emelichev V., Podkapaev D. Quantitative stability analysis for vector problems of 0-1 programming // Discrete Opnimization . – 2010
    . In discussing the notion of the approach of a variable magnitude to a fixed limiting value, and especially in proving the theorem that every magnitude which grows continuously but not beyond all limits, must certainly approach a limiting value, I had recourse to geometric evidences. … This feeling of dissatisfaction was so overpowering that I made the fixed resolve to keep mediating on the question till I should find a purely arithmetic and perfectly rigorous foundation for the principles of infinitesimal analysis.
    He defined a real number to be a pair (L, R) of sets of rationals which have the following properties.
    a. Every rational is in exactly one of the sets
    b. Every rational in L is < every rational in R
    Such a pair is called a Dedekind cut (Schnitt in German). You can think of it as defining a real number which is the least upper bound of the "Left-hand set" L and also the greatest lower bound of the "right-hand set" R. If the cut defines a rational number then this may be in either of the two sets.
    It is rather a rather long (and tedious) task to define the arithmetic operations and order relation on such cuts and to verify that they do then satisfy the axioms for the Reals — including even the Completeness Axiom.
    Richard Dedekind, along with Bernhard Riemann was the last research student of Gauss. His arithmetisation of analysis was his most important contribution to mathematics, but was not enthusiastically received by leading mathematicians of his day, notably Kronecker and Weierstrass. His ideas were, however, warmly welcomed by Jordan and especially by Cantor with whom he became firm friends.

    Introduction initial data of many problem of discrete optimization has the approached character. Therefore the analysis of stability of decisions is actual at fluctuations of parameters of a problem. Numerous publications (see, e.g., [1]) are devoted research of various as pests of stability of scalar and vector problems of discrete optimization. Questions of stability not only decisions of problems of discrete optimization, but also algorithms of their decision (see, e.g., [2, 3]) are actual. One of possible variants of research of stability local (gradient) algorithms is the finding of chance of the guaranteed

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: