Introduction to Graph Theory (11 page)

Figure 37

Figure 38

One final thing. Since isomorphism emancipates us from specific labelings, we may as well, whenever convenient, do away with labels altogether. Consequently we will often represent graphs by unlabeled diagrams.

Example.
We will speak of the graphs in
Figure 39
as respectively
K
₂
,
C
₅
, and
N
₃
because they are respectively isomorphic to
K
₂
,
C
₅
, and
N
₃
as originally defined.

Figure 39

The number of graphs having a given
v

I want to tell you something of what's known about the size of the “ballpark” in which we are playing our game.

If equality were the criterion for judging graphs to be “the same”, and therefore the criterion for judging them to be “different”, we would have to say that there “are” an infinite number of graphs with, say,
v
= 2 and
e
= 1, as such a graph can be labeled in infinitely many ways (
Figure 40
). To a mathematician, who by training and inclination probes for basic structure, this would be a ridiculous situation. Labels are ephemeral; they tell you about as much about the structure of a graph as the list of colors tells you about the structure of a painting.

Isomorphism is the criterion instead, because it is in accord with the mathematician's perception that, for graphs with two vertices and one edge, there is only one basic design. Every graph with
v
= 2 and
e
= 1 is isomorphic to
K
₂
(the first graph in
Figure 39
); we will express this by saying “up to isomorphism,
K
₂
is the only graph with
v
= 2 and
e
=1”, or more simply “
K
₂
is the only graph with
v
= 2 and
e
= 1”, it being understood that we judge graphs to be “different” only if they are not isomorphic.

Similarly, as every graph with two vertices and no edges is isomorphic
to
N
₂
,
N
₂
is the only graph with
v
= 2 and
e
= 0. So in all there are two graphs having
v
= 2.

Figure 40

Of course all graphs with
v
= 1 are isomorphic to
K
₁
(also named
N
₁
), so there is only one graph with
v
= 1.

You can check for yourself that no two of the graphs in
Figure 41
are isomorphic, and that every graph with three vertices is isomorphic to one of them. Therefore those four are the only graphs having
v
= 3.

Figure 41

Let's determine how many graphs there are with
v
= 4. The situation is more complicated than
v
= 1,
v
= 2, or
v
= 3, so I'll proceed systematically.

On a piece of paper I arrange seven columns headed by “
e
= 0”, “
e
= 1”, “
e
= 2”, and so on, up to “
e
= 6”. A graph with four vertices can have no more than six edges, as complete graphs have all possible edges and
K
₄
has
e
= 6 by
Theorem 2
.

In the “
e
= 0” column I draw
N
₄
. Obviously any other graph with
v
= 4 and
e
= 0 will be isomorphic to
N
₄
, so that's all for that column.

Now I jump to the “
e
= 6” column and draw
K
₄
, which is the complement of
N
₄
. I do the chart by complements because it has occurred to me (think about this) that isomorphic graphs must have isomorphic complements, and nonisomorphic graphs must have nonisomorphic complements.

Back to the “
e
= 1” column. It's clear to me that this column will contain only one graph. (If you're not convinced, draw lots of graphs with
v
= 4 and
e
= 1 and then prove they're all isomorphic.)

Now I'll put the complement of the “
e
= 1” graph under “
e
=5”. I'm confident there is no other graph with
e
= 5, reasoning as follows: if there were two nonisomorphic graphs with
e
= 5, then their complements would be nonisomorphic graphs with
e
= 1; but I'm satisfied there's only one graph with
e
= 1.

A graph with
v
= 4 and
e
= 2 can be constructed in two ways, with the edges separate or joined. So under “e = 2” I draw the two graphs of
Figure 42
. They are not isomorphic, and every graph with
v
= 4 and
e
= 2 is isomorphic to one of them.

Now in the column headed “
e
= 4” I draw the complements of the graphs in
Figure 42
.

The “
e
= 3” column is the only one left. This column isn't paired with a complementary column because there are an odd number of columns; if a graph has
v
= 4 and
e
= 3, then its complement also has
v
= 4 and
e
= 3. I start with the first graph of
Figure 42
, and add an edge in all possible ways (
Figure 43
). These four graphs are all isomorphic, so they amount to only one graph for the “
e
= 3” column. Next I take the second graph of
Figure 42
, and add an edge in all possible ways (
Figure 44
). Of these four graphs the first and
last are nothing new, as they are isomorphic to one another and to the graphs of
Figure 43
. But the middle two are new: they are not isomorphic to each other or to the graph of
Figure 43
. I conclude that there are three patterns for a graph with
v
= 4 and
e
= 3.

Figure 42

Figure 43

My chart is finished. I have reproduced it in
Figure 45
. There are eleven graphs with
v
= 4.

If you're wondering where the “square” is, it's the first graph in the “
e
= 4” column. It's twisted because of the particular drawing I made of its complement, which is the first graph under “
e
= 2”. If not having a recognizable square bothers you, you can redo the first graph under “
e
= 2” to look like an
X
.

By the way, some people get the impression that the graphs we've given specific names to are the only graphs there are. If you are one of these people, please notice that of the graphs in
Figure 45
only three have been named—
N
₄
,
C
₄
, and
K
₄
.

Figure 44

You may wonder how many graphs there are with
v
= 5,
v
= 6 etc. The totals get large very fast: