This is a list of technical terms, notations, and names in the Graph Theory Exercises booklet. It gives the page where each term is defined.
⌊x⌋ ... 10
⌊x⌋ ... 36
⌈x⌉ ... 72
V(2) ... 8
Adj ... 17
VG ... 8
EG ... 8
n(G) ... 8
m(G) ... 8
c(G) ... 37
d(v) ... 17
d(X) ... 27
Kn ... 8
Kp,q ... 15
Qk ... 12
L(G) ... 14
N(v) ... 17
N(X) ... 28
X ⊂ Y ... 24
Y ⊃ X ... 24
A ⊕ B ... 28
G ⊆ H ... 24
G ∪ H ... 22
G ∩ H ... 22
G[X] ... 24
G ≅ H ... 57
G(n) ... 56
G−v ... 24
G−X ... 24
G−e ... 24
G−A ... 24
α(G) ... 69
α′(G) ... 93
β(G) ... 79
γ(G, S) ... 106
δ(G) ... 17
δ(X) ... 27
Δ(G) ... 17
κ(G) ... 129
κ′(G) ... 125
μ(G) ... 17
o(G) ... 105
χ(G) ... 81
χ′(G) ... 109
ω(G) ... 75
∂(X) ... 27
∇(X) ... 27
A
α(G) ... 69
α′(G) ... 93
acyclic ... 115
adjacency matrix ... 9
adjacent ... 8
edges ... 14
edges ... 93
vertices ... 8
algorithm
approximation ... 80
greedy ... 71
greedy ... 84
greedy ... 87
greedy ... 111
Hungarian ... 101
Kruskal ... 117
max-flow min-cut ... 124
Prim ... 117
alkanes ... 9
almost every ... 56
alternating path ... 93
Appel ... 89
approximation algorithm ... 80
articulation ... 43
augmenting path ... 94
B
β(G) ... 79
Barnette ... 136
Berge ... 91
BFS ... 120
bicolorable ... 65
bicoloring ... 65
biconnected ... 43
biconnected ... 129
edge- ... 42
bipartite ... 15
complete ... 15
bipartition ... 15
of set ... 65
bishop (chess) ... 11
Bollobás ... 5
boundary of face ... 51
breadth-first search ... 120
bridge ... 40
C
c(G) ... 37
Catlin ... 83
center ... 121
certificate ... 68
certificate ... 87
certificate ... 98
certificate ... 108
certificate ... 126
certificate ... 130
certificate ... 140
chess bord ... 10
child of a vertex ... 45
Chinese postman ... 140
chromatic
index ... 109
number ... 81
Chudnovsky ... 91
Chvátal ... 134
circuit ... 20
cover ... 137
decomposition ... 137
double cover ... 141
even ... 67
minimum ... 119
odd ... 67
circumference ... 131
clique ... 75
cover ... 82
number ... 75
closed
trail ... 139
walk ... 33
coboundary ... 27
collection ... 56
color exchange heuristic ... 112
colorable ... 81
k-colorable ... 81
coloring
minimum ... 81
minimum ... 109
of faces ... 89
of vertices ... 81
k-coloring ... 81
comparability ... 14
complement ... 8
complete ... 8
component ... 37
conjecture
Barnette ... 136
Berge ... 91
Chvátal ... 134
circuit double cover ... 141
Hadwiger ... 90
connected ... 34
k-connected ... 129
connectivity ... 125
connectivity ... 129
connector ... 115
connects u to v ... 20
cover ... 79
vertex ... 79
covering
by circuits ... 137
cube ... 12
k-cube ... 12
cut ... 27
edge ... 40
vertex ... 43
cycle ... 33
cycle ... 139
D
D ... 6
δ(G) ... 17
δ(X) ... 27
Δ(G) ... 17
d(v) ... 17
d(X) ... 27
∂(X) ... 27
degree
average ... 17
maximum ... 17
minimum ... 17
of a face ... 51
of a set of vertices ... 27
of a vertex ... 17
sequence ... 63
diameter ... 122
Dirac ... 130
Dirac ... 134
Dirac ... 145
disjoint graphs ... 22
dist( ) ... 119
distance ... 119
tree ... 120
dual de plane map ... 52
E
E ... 6
o E ... 6
! E ... 6
!! E ... 6
* E ... 6
*! E ... 6
*o E ... 6
▷ E ... 6
E ♥ ... 6
EG ... 8
eccentricity ... 121
edge ... 8
coloring ... 109
cover ... 107
endpoints ... 8
edge-biconnected ... 42
edge-biconnected ... 125
k-edge-connected ... 125
edge-connectivity ... 125
edges
adjacent ... 14
adjacent ... 93
multiple ... 52
parallel ... 52
Edmonds ... 106
Egerváry ... 100
empty graph ... 8
Erdös ... 64
Erdös ... 113
Euler ... 53
Euler ... 139
Eulerian
cycle ... 139
trail ... 139
Euler's formula ... 53
even girth ... 121
F
face of a map ... 51
flow ... 123
internally disjoint ... 127
forest ... 45
fringe ... 27
G
γ(G, S) ... 106
G(n) ... 56
Gallai ... 64
Gallai ... 86
Gallai ... 106
girth ... 119
graph ... 8
acyclic ... 45
bicolorable ... 65
biconnected ... 43
biconnected ... 129
bipartite ... 15
bishop ... 11
Catlin ... 83
k-colorable ... 81
comparability ... 14
complement ... 8
complete ... 8
complete bipartite ... 15
cubic ... 17
dual ... 52
edge-biconnected ... 42
edge-biconnected ... 125
empty ... 8
grid ... 10
Heawood ... 31
Heawood ... 121
interval ... 14
king ... 12
Kneser ... 12
knight ... 11
line ... 14
of a plane map ... 50
of a square matrix ... 13
of Europe ... 13
of the faces ... 52
outerplanar ... 55
perfect ... 91
Petersen ... 12
planar ... 23
planar ... 51
plane ... 50
queen ... 10
random ... 56
regular ... 17
rook ... 11
Turán ... 73
words ... 12
graph design ... 63
graphic sequence ... 63
greedy ... 71
greedy ... 84
greedy ... 111
grid ... 10
H
Hadwiger ... 90
Hajós ... 90
Haken ... 89
Hall ... 102
Hamilton ... 131
Hamiltonian
circuit ... 131
path ... 131
Heawood ... 31
Heawood ... 121
hexagon ... 20
hydrocarbons ... 9
I
independence matrix ...9
incident ... 8
independence number ... 69
independent set ... 69
induced graph ... 24
induction ... 24
induction ... 132
internal vertex ... 20
internal vertex ... 127
internally disjoint ... 43
internally disjoint ... 127
intersection of graphs ... 22
interval ... 14
isolated (vertex) ... 17
isolator ... 29
isomorphism ... 57
isthmus ... 40
K
Kn ... 8
Kp,q ... 15
n ... 8
κ(G) ... 129
κ′(G) ... 125
king (chess) ... 12
Kirkman ... 131
Kneser ... 12
knight (chess) ... 11
König ... 100
König ... 112
Kruskal ... 117
Kuratowski ... 144
L
L(G) ... 14
leaf ... 45
length
of a circuit ... 20
of a path ... 20
of a trail ... 32
of a walk ... 32
of a walk ... 139
line graph ... 14
lines (of plane map) ... 50
longest
circuit ... 131
path ... 131
loop ... 8
loop ... 52
Lovász ... 5
Lovász ... 12
Lovász ... 91
M
m(G) ... 8
μ(G) ... 17
matching ... 93
maximum weight ... 107
perfect ... 93
matrix
adjacency ... 9
incidence ... 9
maximal ... 69
maximal ... 93
maximal vs maximum ... 30
maximal vs maximum ... 69
maximal vs maximum ... 93
maximal vs maximum ... 115
maximum ... 25
maximum ... 69
maximum ... 93
flow ... 123
Menger ... 124
Menger ... 128
minimal vs minimum ... 115
minor ... 47
multiple edges ... 8
multiple edges ... 52
N
n(G) ... 8
N(v) ... 17
N(X) ... 28
neighbor ... 8
neighborhood ... 17
NP-complete ... 5
NP-hard ... 5
number of colors ... 81
number of colors ... 109
O
o(G) ... 105
ω(G) ... 75
odd
circuit ... 65
component ... 105
girth ... 121
hole ... 91
origin of walk ... 32
outerplanar ... 55
P
parallel edges ... 8
parallel edges ... 52
parent of vertex ... 45
parity ... 67
partial order ... 14
partition ... 15
path ... 20
endpoints ... 20
even ... 67
maximal ... 30
maximum ... 30
odd ... 67
pentagon ... 20
perfect
elimination scheme ... 85
graph ... 91
matching ... 93
permutation ... 20
permutation ... 45
Petersen ... 12
planar ... 23
planar ... 51
planar ... 143
plane map ... 50
points (of plane map) ... 50
Prim ... 117
problem
Chinese postman ... 140
traveling salesman ... 135
proper subgraph ... 24
Q
Qk ... 12
queen (chess) ... 10
R
radius ... 121
random ... 56
regular ... 17
Robertson ... 89
Robertson ... 91
rook (chess) ... 11
root of tree ... 45
Roy ... 86
S
saturated vertex ... 93
self-complementary ... 60
separates ... 32
separates ... 123
separates ... 127
separator ... 127
Seymour ... 89
Seymour ... 91
Seymour ... 141
shortest path ... 119
simple graph ... 8
slither ... 96
spanning
subgraph ... 24
tree ... 115
square ... 20
stability number ... 69
stable set ... 69
star ... 15
subcontraction ... 47
subdivision ... 48
subgraph ... 24
maximal ... 37
subpartition ... 47
support of plane map ... 51
symmetric difference ... 28
symmetric difference ... 95
Szekeres ... 141
T
terminus of walk ... 32
theorem
Berge ... 95
Brooks ... 85
Dirac ... 130
Dirac ... 134
Erdös and Gallai ... 64
Euler ... 138
Four Color ... 89
Gallai & Roy ... 86
Hall ... 102
Havel and Hakimi ... 64
König ... 112
König–Egerváry ... 100
Kuratowski ... 144
Menger ... 124
Menger ... 128
Turán ... 73
Tutte ... 105
Tutte ... 135
Tutte–Berge ... 106
Veblen ... 138
Vizing ... 113
Wagner ... 144
Thomas ... 89
Thomas ... 91
topological minor ... 47
trail ... 32
trail ... 139
traveling salesman ... 135
tree ... 45
triangle ... 20
triangle inequality ... 120
trivial cut ... 27
TSP ... 135
Turán ... 73
Tutte ... 105
Tutte ... 135
U
union of graphs ... 22
unordered pair ... 8
uses k cores ... 81
V
VG ... 8
vertex ... 8
cover ... 79
isolated ... 17
W
Wagner ... 144
walk ... 32
walk ... 139
closed ... 33
from v to w ... 32
from v to w ... 139
origin ... 32
simple ... 32
terminus ... 32
weight of an edge ... 107
weight of an edge ... 117
wheel ... 22
Wilson ... 113
words ... 12
X
χ(G) ... 81
χ′(G) ... 109
Y
Younger ... 5