Introduction to Graph Theory (46 page)

K
₁
, as platonic,
118
;

see also
N
₁

K
₃
,
57
,
168
;

as line graph,
193
;

expansions of,
93
;

supergraphs of,
93
,
106
,
128
,
139

K
₄
, as platonic,
118
,
123
;

chromatic number of,
130
;

connectivity of,
114–115
;

faces of,
99–100
;

genus of,
144
,
154
;

line graph of,
192

K
₅
, crossing number of,
170
;

expansions of,
75–76
,
80
,
94
,
116
;

expansions of supergraphs of,
82–83
,
94
;

faces of,
148
;

genus of,
144
,
154
;

how to find expansions of,
86–87
;

nonplanarity of,
70–71
,
106
;

supergraphs of,
94
;

supergraphs of expansions of,
80–85
,
94

K
₆
, crossing number of,
170
;

genus of,
145
,
154

K
₇
as 1-platonic,
162
,
168
;

as skeleton of toroidal polyhedron,
169

Kaliningrad,
188

Kelvin, Lord (William Thomson),
7

Kempe, A. B.,
130

Kepler, Johannes,
123

Königsberg, see “Seven Bridges of Königsberg”

Kramer's
The Nature and Growth of Modern Mathematics
,
109

Kuratowski's Theorem,
84
;

analogs of,
147

K
_v
, see complete graphs

Law of Excluded Middle,
18
,
56
,
98

L
(
G
), see line graph

line graph,
191–193

loop,
24

Map Coloring Problem,
137
;

partial solution,
138

maps,
136–139

mathematical induction,
101–104
,
111–112
,
131–136

multigraphs,
24
,
182–188

N
₁
, as connected,
98
;

as polygonal,
111
;

see also
K
₁

nonplanar graphs,
64
;

and coloring,
128
;

and connectivity,
116
;

and genus,
147
;

characterization of,
84
;

counting the faces of,
148
;

demonstrating nonplanarity,
64–65
,
85–93
,
114
,
116
;

expansions of
UG
or
K
₅
,
80
;

supergraphs of,
72
;

supergraphs of expansions of
UG
or
K
₅
,
80–85

null graphs,
26
(see also
47–49
);

as disconnected (except
N
₁
),
98
;

chromatic number of,
139
;

complements of,
31
;

regularity of,
117
;

walks in,
97

null set,
14

number, of nonisomorphic graphs,
50–56
;

of unequal graphs,
61–62

N
_v
, see null graph

octahedron,
120–125

odd vertex,
175–176
,
188
,
191
;

in a multigraph,
184–185
,
187

one-to-one correspondence,
34–35
,
57

Ore's
The Four-Color Problem
,
139

The Organon
,
8

p
, see component

P
₃
,
105

P
₄
,
105

path graphs,
56
,
178–182
,
190

P
(
d
,
n
),
158–162
,
168

Petersen graph,
93
,
170

“pieces” of a graph,
42–47
;

see also component

pigeonhole principle,
69
,
71
,
94

planar and connected graphs,
104–107
,
116
;

see also Euler's Formula, polygonal graphs

planar graphs,
64
,
141
;

and coloring vertices,
128
,
130–136
;

and maps,
136
;

characterization of,
85
;

demonstrating planarity,
64
,
85–93
;

duals of,
124–125
,
137–138
;

genus of,
142–144
;

maximal,
116
;

preserved by isomorphism,
94
;

subgraphs of,
72
;

see also planar and connected graphs

Plato,
6
,
8
,
117
,
123

platonic graphs,
117–125
;

see also
g
-platonic graphs

platonic solids,
123

Plato's “world of Ideas,”
38

Poincaré, Henri,
109

Polya Enumeration Theorem,
54

polygon,
121–122

polygonal graphs,
100
,
102–105
,
115–116
,
118
,
139

polyhedron,
121–122
;

toroidal,
168–170

properties preserved by isomorphism,
41–47
,
57–59
,
94

pseudograph,
24

pure vs. applied mathematics,
ix
,
1–9

Pythagoras,
7
,
15

Pythagorean paradox,
15–17

Pythagoreans,
15
,
122–123

Pythagorean Theorem,
15

P
_v
, see path graphs

regular graphs,
117–118
,
123–124
,
158

regular polygon,
121–122

regular polyhedron,
121–122

Ringel, G.,
156

Russell, Bertrand,
9
,
17–18

Russell's paradox,
17–19
,
56

S
₀
,
S
₁
,
S
₂
, ...,
S
_g
, ...,
S
_n
, etc.,
141
;

and genus,
142

Scientific American
,
170

self-complementary graphs,
57

“The Seven Bridges of Königsberg,”
97
,
185–188

set,
12–15

skein,
24
,
182

steel balls and rubber bands,
39–41

Stein's
Mathematics: the Man-Made Universe
,
176
,
178

subgraphs,
32
(see also
47–49
);

as constructed by selective erasing,
32
,
72–73
,
77–78
;

distribution of,
57–59
;

of planar graphs,
72

subgraph distribution preserved by isomorphism,
57–59

subsst,
14
,
56

supergraphs,
72
,
154
;

as constructed by selective augmentation,
72
,
77–80
;

expansions of supergraphs of
UG
or
K
₅
,
82–83
,
94
;

of cyclic graphs,
191
;

of expansions of
UG
or
K
₅
,
80–85
,
94
;

of
K
₃
93
,
106
,
128
,
139
;

of
K
₅
94
;

of nonplanar graphs,
72
;

of
UG
,
94

T
₄
(called “the star graph on 4 vertices”),
106

tetrahedron,
120–123

Timaeus
,
123

T
(
G
), see trisection graphs

Theory of Types,
18

topology,
ix
,
108–111

toroidal polyhedron,
168–170

torus,
141

trisection graphs,
192–193

Two Color Theorem,
139

UG
, see utility graph

unlabeled diagrams,
49
,
128

utility graph,
27
(see also
47–49
);

and euler walks,
173
;

as puzzle,
27
,
62–63
,
66
;

complement of,
31
;

crossing number of,
170
;

expansions of,
75–76
,
80
,
94
,
116
;

expansions of supergraphs of,
82–83
,
94
;

faces of,
148
;

genus of,
144
;

how to find expansions of,
86
;

nonplanarity of,
66–70
,
107
;

regularity of,
117
;

supergraphs of,
94
;

supergraphs of expansions of,
80–85
,
94

v
,
19

vertex,
19
;

even,
173
,
175
,
188
;

odd,
175–176
,
188
,
191
;

even in a multigraph,
184
;

odd in a multigraph,
184–185
,
187

vertex set,
19

Vollmerhaus, H.,
147

walk,
97
;

open,
172
;

closed,
172
;

in a multigraph,
183
;

see also euler walk and hamilton walk

wheel graphs,
56
,
125
,
190

Wordsworth, William,
9

(quotation: the lines are from
The Prelude
, Book 6)

W
_v
, see wheel graphs

X
, see chromatic number

X
, see complement, chromatic number of
X
(
S
_n
), see chromatic number of the surface
S
_n

Youngs, J. W. T.,
156

SPECIAL SYMBOLS

{...}
as “the set of,”
13
; as “the least integer greater than or equal to,”
154

⊂
“is a subset of,”
14

ø
“the empty set,”
14

 
(over the name of a graph as in
G
,
C
₄
) “the complement of,”
31

≅
“is isomorphic to,”
35

[...]
“the greatest integer less than or equal to,”
165

<
“less than”

≤
“less than or equal to”

>
“greater than”

≥
“greater than or equal to”