Introduction to Graph Theory (16 page)

Figure 66

Let us now prove that these are in fact examples of a new type of nonplanar graph.

Consider graph a). It is not a supergraph of
UG
because
UG
has six vertices of degree 3 and so any supergraph of
UG
must contain six vertices with degrees greater than or equal to 3; but this is not true of graph a). Graph a) is not a supergraph of
K
₅
because
K
₅
consists of five vertices each adjacent to the other four and so any supergraph of
K
₅
must also contain five vertices each adjacent to the other four; but the only reasonable choice of five vertices from graph (a)—1, 2, 3, 4, and 5—is missing an edge, for 3 is not adjacent to 4.

All that remains is to show that graph a) is nonplanar. Suppose for the sake of argument that graph a) is planar. Then it can be drawn in a plane without edge-crossings. Suppose that this has been done. Then we can take the crossing-free drawing of graph a) and find vertex 6, which is easy to do since vertex 6 is the only vertex of degree 2. Having found vertex 6 we can erase it and join its two incident edges to one another, forming one new edge where formerly there were two edges and vertex 6.

You might object that this procedure is illegal because we have erased a vertex without also erasing its incident edges, contrary to what we said about erasing on page 32. But that restriction is pertinent only when our goal is a subgraph. We can certainly erase vertex 6 and join the two edges left dangling; it's just that what we end up with will not be a subgraph of graph a).

It is clear that this procedure creates no edge-crossings, and that the graph we have as a result is
K
₅
. Since we started with a plane drawing of graph a) that was crossing-free, the altered drawing is a crossing-free plane drawing of
K
₅
. Of course, no such drawing can possibly exist, as
K
₅
is nonplanar. This contradiction renders untenable our original supposition that graph a) is planar, so graph a) must be nonplanar.

In a similar way we can show that graph b) is a nonplanar graph, but is not a supergraph of either
UG
or
K
₅
. It is not a supergraph of
UG
because
UG
has six vertices, each of which is joined to three of the other five, and consequently any supergraph of
UG
must contain a collection of six vertices, each of which is joined to three of the other five; but since
Q
has degree 2, the only possible collection of six vertices from graph b) is
A, B, C, X, Y, Z
, and
C
and
Z
are joined to only two of the other five. Graph b) is not a supergraph of
K
₅
because
K
₅
has five vertices of degree 4 and consequently any supergraph of
K
₅
must contain five vertices whose degrees are at least 4; but graph b) has only vertices of degrees 2 and 3. Finally, if graph b) were planar we could take a crossing-free drawing of graph b) in a plane, erase vertex
Q
and join the dangling edges, and thereby create a crossing-free plane drawing of
UG
, which we know is impossible; so graph b) must be nonplanar.

Expansions

Having seen the two examples of the last section, it seems likely that other similarly-constructed graphs, like those in
Figure 67
, would also turn out to be nonplanar graphs that are not supergraphs of
UG
or
K
₅
. So we are motivated to define a new term.

Definition 20
.
If some new vertices of degree 2 are added to some of the edges of a graph
G
, the resulting graph
H
is called an
expansion
of
G
.

Figure 67

Examples
.
The graph of
Figure 67a
is an expansion of
K
₅
; b) is another expansion of
K
₅
; c) is an expansion of
UG
. The graph of
Figure 64a
is an expansion of 64b.

In a mathematical context the word “some” includes the possibility “none”. By the above definition therefore, every graph is an expansion of itself.

It's easy to confuse “expansion” and “supergraph”. As the distinction is crucial to the rest of this chapter, I want to spend some time discussing the two notions.

Both expansions and supergraphs are “augmentations” of a graph, but they are accomplished by different procedures. In making an expansion there is only one thing we are allowed to do (provided we do anything at all): splice new vertices of degree 2 into the edges. That amounts to severing old connections between vertices and inserting intermediary vertices. Though I realize that I can physically “add” vertices of degree 2 to a diagram with only a pencil, I prefer to interpret expansion as something done with pencil and eraser, because this interpretation takes cognizance of the fact that the process of expansion not only augments the structure of a graph, but also subtracts from it.

To make an expansion of a graph,

1)
  
you don't have to do anything (every graph is an expansion of itself);

2)
  
if however you choose to do something, this is what you do: with an eraser, erase some holes in some of the edges, then with a pencil fill the holes with vertices of degree 2.

This is illustrated in
Figure 68
. The first drawing is the original graph; in the second drawing edges have been selected and holes erased; and the third drawing shows the finished expansion.

As opposed to the process of expansion, in which the only thing we are allowed to do is splice new vertices of degree 2 into the edges, in making a supergraph splicing new vertices (of any degree) into the edges is the only thing we are
not
allowed to do. We mentioned this on page 72 and cited as an example the graphs of
Figure 64
,
C
₄
and
K
₃
. In order for
C
₄
to be a supergraph of
K
₃
,
K
₃
would (by
Definition 19)
have to be a subgraph of
C
₄
. And I said on page 72 that “using only an eraser you can never make
C
₄
look like
K
₃
,” so
K
₃
is not a subgraph of
C
₄
. I was referring to the “selective erasing” process whereby we interpreted subgraph extraction back on page 32. It might be helpful if I repeated it here.

To make a subgraph of a graph,

Figure 68

1)
  
You don't have to do anything (every graph is a subgraph of itself);

2)
  
if however you choose to do something, this is what you do: with an eraser erase however many vertices and/or edges as you like, subject to the restriction that when you erase a vertex you must also erase all edges incident to it.

With this interpretation it's clear that
K
₃
is not a subgraph of
C
₄
and therefore that
C
₄
is not a supergraph of
K
₃
. As
C
₄
can be produced from
K
₃
by splicing a vertex into one edge, we should prohibit splicing whenever the goal is the construction of a supergraph.

To make a supergraph of a graph,

1)
  
you don't have to do anything (every graph is a supergraph of itself);

2)
  
if however you choose to do something, this is what you do: with a pencil, add as many vertices as you like, provided you don't splice them into existing edges; and add as many edges as you like, anywhere you like—new edges may join two original vertices, or two new vertices, or one original vertex and one new vertex.

With these interpretations we see that the processes of expansion and making a supergraph involve different tools. To make an expansion you use both pencil and eraser, while to make a supergraph you use only a pencil (and to make a subgraph you use only an eraser).

Not only are expansions and supergraphs accomplished by different procedures involving different tools, but they usually have different results as well. That is, an expansion of a graph
G
is usually not a supergraph of
G
, and a supergraph of
G
is usually not an expansion of
G
. For example we have already seen that
C
₄
is an expansion of
K
₃
but not a supergraph of
K
₃
.
Figure 69
provides an example of the reverse situation. The first graph is a supergraph of
K
₃
. It was constructed from
K
₃
using only a pencil, by drawing one new vertex and one new edge. It is not an expansion of
K
₃
because the new vertex was not spliced into an edge, and besides it is not of degree 2.

Figure 69

I said that an expansion is “usually” not a supergraph, and vice versa. There are exceptions.

Example
. In
Figure 70
, a) is a supergraph of b) from the perspective that 1 corresponds to 3 with vertex 2 and edge {1,2} added on with a pencil. From another perspective a) is an expansion of b): 2 corresponds to 3 with vertex 1 spliced in with eraser and pencil.

Exceptions notwithstanding, it is generally true that expansions and supergraphs are different, and so it is important to keep the notions distinct in your mind.

The graph of
Figure 71a
is not an expansion of
Figure 71b
. This is because
Definition 20
insists that spliced vertices have degree 2. So we see that an expansion of a graph has the same number of edge-crossings as the original. It is this property that accounts for the following theorem.