Discrete Mathematics: Elementary and Beyond

Index 289

indirect proof, 37, 90, 92, 93, 142,
159, 192
induction, 25–31, 41, 44, 53, 61,
66, 68, 69, 71, 90, 98,
114, 129, 144, 183, 198,
203, 208
simultaneous, 70
induction hypothesis, 27, 29, 53,
68, 98, 145, 198, 203,
208
integer part, 15
intersection of sets, 6
irrational number, 92
isomorphic, 146

Kempe, A.B., 206
key of cryptosystem, 242
private, 247
public, 248
Kirkman, T.P., 228
K ̈onig, D., 166, 169
K ̈onigsberg bridges, 136
Kruskal’s Algorithm, 159

labeled tree, 146, 148
Lam, C.W.H., 220
Latin square, 229–232
orthogonal, 230
Law of Large Numbers, 77, 80
Law of Small Numbers, 83
Law of Very Large Numbers, 83
least common multiple, 99
line at infinity, 218
logarithm, 15, 31, 32, 37–40, 56,
59–62, 95, 102
loop, 126
Lucas numbers, 74

magic square, 230
Maple, 122, 246
Marriage Theorem, 169, 223
matching, 165–178
greedy, 172
perfect, 165
Mathematica, 122

Miller–Rabin test, 121

minimal criminal, 90

modular arithmetic, 109

modulus, 105

multigraph, 126, 207

multiple, 87

node, 126

adjacent, 126

degree, 127, 166, 171, 176,

203, 207, 210

father, 142

neighbors, 126

son, 143

noisy channel, 232

one-time pad, 242

one-to-one correspondence, 14,

150

P ́olya, G., 155

Pascal’s Triangle, 49, 77

Pascal, Blaise, 49

password, 246

path, 130

augmenting, 173

endpoints, 131

length, 131

permutation, 17

Petersen graph, 139, 195

Pigeonhole Principle, 35, 37, 114,

202, 230, 240

plain text, 242

planar code, 153

planar graph,seegraph, planar

planar map, 189, 205, 206, 210

plane

affine, 218

coordinates, 219

order, 218

Euclidean, 211, 219

Fano, 211, 221, 224, 236

projective, 217

order, 217

Tictactoe, 213, 221, 224