Read Introduction to Graph Theory Online

Authors: Richard J. Trudeau

Introduction to Graph Theory (46 page)

BOOK: Introduction to Graph Theory
8.14Mb size Format: txt, pdf, ePub
ads

K
1
, as platonic,
118
;

see also
N
1

K
3
,
57
,
168
;

as line graph,
193
;

expansions of,
93
;

supergraphs of,
93
,
106
,
128
,
139

K
4
, 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
5
, 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
6
, crossing number of,
170
;

genus of,
145
,
154

K
7
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
1
, as connected,
98
;

as polygonal,
111
;

see also
K
1

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
5
,
80
;

supergraphs of,
72
;

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

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

as disconnected (except
N
1
),
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
3
,
105

P
4
,
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
0
,
S
1
,
S
2
, ...,
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
5
,
82–83
,
94
;

of cyclic graphs,
191
;

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

of
K
3
93
,
106
,
128
,
139
;

of
K
5
94
;

of nonplanar graphs,
72
;

of
UG
,
94

T
4
(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
4
) “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”

BOOK: Introduction to Graph Theory
8.14Mb size Format: txt, pdf, ePub
ads

Other books

Mafia Prince: Inside America's Most Violent Crime Family by Phil Leonetti, Scott Burnstein, Christopher Graziano
Magic Edge by Ella Summers
Dominant Species by Marks, Michael E.
Two Masters for Alex by Claire Thompson
Music of the Swamp by Lewis Nordan
Ciudad piloto by Jesús Mate
Clan and Crown by Tracy St. John