-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathmath239.html
More file actions
715 lines (715 loc) · 102 KB
/
math239.html
File metadata and controls
715 lines (715 loc) · 102 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
<!DOCTYPE html>
<html xmlns="http://www.w3.org/1999/xhtml" lang="" xml:lang="">
<head>
<meta charset="utf-8" />
<meta name="generator" content="pandoc" />
<meta name="viewport" content="width=device-width, initial-scale=1.0, user-scalable=yes" />
<title>math239</title>
<style type="text/css">
code{white-space: pre-wrap;}
span.smallcaps{font-variant: small-caps;}
span.underline{text-decoration: underline;}
div.column{display: inline-block; vertical-align: top; width: 50%;}
</style>
<link rel="stylesheet" href="../pandoc.css" />
<script src="https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.9.0/katex.min.js"></script>
<script>document.addEventListener("DOMContentLoaded", function () {
var mathElements = document.getElementsByClassName("math");
for (var i = 0; i < mathElements.length; i++) {
var texText = mathElements[i].firstChild;
if (mathElements[i].tagName == "SPAN") { katex.render(texText.data, mathElements[i], { displayMode: mathElements[i].classList.contains("display"), throwOnError: false } );
}}});</script>
<link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.9.0/katex.min.css" />
<!--[if lt IE 9]>
<script src="//cdnjs.cloudflare.com/ajax/libs/html5shiv/3.7.3/html5shiv-printshiv.min.js"></script>
<![endif]-->
</head>
<body>
<h1 id="math239">MATH239</h1>
<h1 id="enumeration">Enumeration</h1>
<h2 id="sets-we-count">Sets We Count</h2>
<ol type="1">
<li><strong>Cartesian Products</strong>, <span class="math inline">A \times B = \{(a, b) | a \in A, b \in B\}</span>, <span class="math inline">A^k = \{(a_1, ..., a_k)|a_i \in A\}</span>.</li>
<li><strong>Disjoint Union</strong>, <span class="math inline">S = S_1 \cup S_2</span>, <span class="math inline">S_1 \cap S_2 = \emptyset</span>, then <span class="math inline">|S| = |S_1| + |S_2|</span>.</li>
</ol>
<p><strong>Binomial Coeff</strong>: How many subsets of <span class="math inline">\{1, ..., n\}</span> have size <span class="math inline">k</span>? <span class="math inline">{n \choose k} = \frac{n!}{(n-k)!k!}</span></p>
<p><strong>Binomial Theorem</strong>: <span class="math inline">(1 + x)^n = \sum_{k = 0}^n{n \choose k}x^k</span>. Proof using counting arguments.</p>
<blockquote>
<p><span class="math inline">(1 + x)^n = \sum a_1a_2...a_n, a_i \in \{1, x\}</span> > Coeff <span class="math inline">x^k</span> represents the number of terms in the sum that have <span class="math inline">x^k</span>. To get <span class="math inline">x^k</span>, we need exactly <span class="math inline">k</span> “x”, and <span class="math inline">n - k</span> “1”. There are <span class="math inline">n \choose k</span> ways so the coeff of <span class="math inline">x^k</span> is <span class="math inline">n \choose k</span>.</p>
</blockquote>
<h1 id="combinatorial-proofs">Combinatorial Proofs</h1>
<blockquote>
<p>Idea: Count a set of objects in 2 different ways. The results must be equal.</p>
</blockquote>
<p>Example: <span class="math inline">2^n = \sum_{k = 0}^n {n \choose k}</span></p>
<blockquote>
<p>Let <span class="math inline">S</span> be the set of all binary strings of length <span class="math inline">n</span>. Then <span class="math inline">|S| = 2^n</span>. We count <span class="math inline">S</span> in a different way. Let <span class="math inline">S_k</span> be the set of all binary strings of length <span class="math inline">n</span> with exactly <span class="math inline">k</span> 0, <span class="math inline">k = 0,...,n</span>. Then <span class="math inline">S = \cup_{k = 0}^n S_k</span>. This is a disjoint union so <span class="math inline">|S| = \sum_{k = 0}^n |S_k|</span>. For each <span class="math inline">k</span>, <span class="math inline">|S_k| = {n \choose k}</span> since we are choosing exactly <span class="math inline">k</span> bits out of <span class="math inline">n</span> bits to be 0. So <span class="math inline">2^n = \sum_{k = 0}^n {n \choose k}</span>.</p>
</blockquote>
<p>Example: <span class="math inline">{n \choose k} = {n - 1 \choose k} + {n - 1 \choose k - 1}</span></p>
<blockquote>
<p>Let <span class="math inline">S</span> be the set of all subsets of ${1, …, n} of size <span class="math inline">k</span>. So <span class="math inline">|S| = {n \choose k}</span>. Let <span class="math inline">S_1</span> be subsets that include the element <span class="math inline">n</span>, let <span class="math inline">S_2</span> be the subsets that do not include the element <span class="math inline">n</span>.<br />
Each subset of <span class="math inline">S_1</span> consists of <span class="math inline">\{n\}</span> union with <span class="math inline">k - 1</span> elements of <span class="math inline">\{1, ..., n - 1\}</span> so <span class="math inline">|S_1| = {n - 1 \choose k - 1}</span>.<br />
Each subset of <span class="math inline">S_2</span> consists of <span class="math inline">k</span> elements of <span class="math inline">\{1, ..., n\}</span>, so <span class="math inline">|S_2| = {n - 1 \choose k}</span>. Since <span class="math inline">S = S_1 \cup S_2</span> is a disjoint union, <span class="math inline">|S| = |S_1| + |S_2|</span>. The result follows.</p>
</blockquote>
<p>Example: <span class="math inline">{n + k \choose n} = \sum_{i = 0}^k {n + i - 1 \choose n - 1}</span></p>
<blockquote>
<p>Let <span class="math inline">S</span> be all subsets of <span class="math inline">\{1, ..., n + k\}</span> of size <span class="math inline">n</span>. Then <span class="math inline">|S| = {n + k \choose n}</span>. Let <span class="math inline">S_i</span> be the subsets of <span class="math inline">\{1, ..., n + k\}</span> of size <span class="math inline">n</span> where the largest element is <span class="math inline">n + i</span>. So <span class="math inline">i = 0, ..., k</span>. Then <span class="math inline">S = \cup_{i = 0}^k S_i</span> is a disjoint union and <span class="math inline">|S| = \sum_{i = 0}^k |S_i|</span>. Each subset <span class="math inline">S_i</span> consists of <span class="math inline">\{n + i\}</span> union with a subset of <span class="math inline">\{1, ..., n + i - 1\}</span> of size <span class="math inline">n - 1</span>. So <span class="math inline">|S_i| = {n + i - 1 \choose n - 1}</span>. The result follows.</p>
</blockquote>
<p>A <strong>bijection</strong> <span class="math inline">f: S \to T</span>.</p>
<ol type="1">
<li><span class="math inline">f</span> is <strong>injective</strong> if every element of <span class="math inline">S</span> is mapped to a distinct element in <span class="math inline">T</span>.</li>
<li><span class="math inline">f</span> is <strong>surjective</strong> if everything in the codomain is mapped to something in the domain.</li>
<li><span class="math inline">f</span> is a <strong>bijection</strong> if <span class="math inline">f</span> is <strong>injective</strong> and <strong>surjective</strong>.</li>
</ol>
<p>Assume <span class="math inline">S, T</span> are finite. If <span class="math inline">f</span> is injective, <span class="math inline">|S| \le |T|</span>. If <span class="math inline">f</span> is surjective, <span class="math inline">|S| \geq |T|</span>. It follows that if <span class="math inline">f</span> is a bijection, <span class="math inline">|S| = |T|</span>.</p>
<p><strong>Theorem</strong>: <span class="math inline">f</span> is a bijection if it has an inverse <span class="math inline">f^{-1}</span>.<br />
An inverse of <span class="math inline">f: S \to T</span> is a function <span class="math inline">f^{-1}: T \to S</span> where for every <span class="math inline">x \in S</span>, <span class="math inline">f^{-1}(f(x)) = x</span> and for every <span class="math inline">y \in T</span>, <span class="math inline">f(f^{-1}(y)) = y</span>.</p>
<p>Example: Let <span class="math inline">S</span> be all subsets of <span class="math inline">\{1, ..., n\}</span>. Let <span class="math inline">T</span> be all binary strings of length <span class="math inline">n</span>.</p>
<blockquote>
<p>Define <span class="math inline">f: S \to T</span> where <span class="math inline">f(A) = s_ns_{n-1}...s_2 s_1</span>. <span class="math display">s_i \begin{cases}1, &\text{if } i \in A \\ 0, &\text{if } i \notin A\end{cases}</span> By our definition, <span class="math inline">f(A)</span> is a binary string of length <span class="math inline">n</span> so <span class="math inline">f(A) \in T</span>. The inverse <span class="math inline">f^{-1}: T \to S</span> where <span class="math inline">f^{-1}(t_n...t_1) = \{i \in \{1, ..., n\} \mid t_i = 1\}</span>. So <span class="math inline">f</span> is a bijection and <span class="math inline">|S| = |T| = 2^n</span>.</p>
</blockquote>
<h1 id="generating-series">Generating Series</h1>
<p>Example: “How many subsets of <span class="math inline">\{1, 2, 3\}</span> have size <span class="math inline">k</span>?”. Define <span class="math inline">S</span> as the set of all subsets of <span class="math inline">\{1, 2, 3\}</span>.</p>
<p>Define the weight <span class="math inline">w</span> of an element <span class="math inline">A</span> to be <span class="math inline">w(A) = |A|</span>. How many elements in <span class="math inline">S</span> have weight <span class="math inline">k</span>?</p>
<p><span class="math inline">\Phi_S(x) = 1 + 3x + 3x^2 + x^3</span>. The coefficient of <span class="math inline">x^k</span> in the generating series is the answer.</p>
<p><strong>Generating Series</strong>: Given set <span class="math inline">S</span> where <span class="math inline">\rho \in S</span> is given a non-negative integer weight <span class="math inline">w(\rho)</span>, the <strong>generating series</strong> of <span class="math inline">S</span> with respect to <span class="math inline">w</span> is <span class="math inline">\Phi_S(x) = \sum_{\rho \in S} x^{w(\rho)}</span>. If <span class="math inline">a_k</span> is the number of elements in <span class="math inline">S</span> of weight <span class="math inline">k</span>, then <span class="math inline">\Phi_S(x) = \sum_{k \ge 0}a_k x^k</span>. The <em>coefficients</em> store the answers to our counting problems.</p>
<p>Notation: <span class="math inline">[x^k]\Phi_S(x)</span> denotes the coefficient of <span class="math inline">x^k</span> in <span class="math inline">\Phi_S(x)</span>.</p>
<p>Example: How many ways can we throw 2 dice to get a sum of <span class="math inline">k</span>?</p>
<blockquote>
<p>Define <span class="math inline">S = \{1, 2, 3, 4, 5, 6\} = \{(a, b) \mid a, b \in \{1, 2, 3, 4, 5, 6\}\}</span>. Define <span class="math inline">w(a, b) = a + b</span>. So <span class="math inline">\Phi_S(x) = (x + x^2 + x^3 + x^4 + x^5 + x^6)^2</span>.</p>
</blockquote>
<h2 id="format-power-series">Format Power Series</h2>
<blockquote>
<p>A formal power series has the form <span class="math inline">A(x) = \sum_{i \ge 0}a_i x_i</span>, where each <span class="math inline">a_i</span> is a well-defined, finite number. The coefficient of <span class="math inline">x_i \in A(x) = a_i</span>, denoted by <span class="math inline">[x_i]A(x)</span>.</p>
</blockquote>
<p><strong>Equality</strong>: Let <span class="math inline">A(x) = \sum_{n \ge 0}a_n x^n</span>, <span class="math inline">B(x) = \sum_{n \ge 0}b_n x^n</span>. <span class="math inline">A(x) = B(x) \Leftrightarrow a_n = b_n \forall n \ge 0</span>.</p>
<h3 id="operations">Operations</h3>
<p><strong>Addition</strong>: <span class="math inline">A(x) + B(x) = \sum_{n \ge 0} (a_n + b_n) x^n</span>. Since <span class="math inline">a_n + b_n</span> is a well-defined finite number, <span class="math inline">A(x) + B(x)</span> is also a formal power series (<em>closed under addition</em>).</p>
<p><strong>Multiplication</strong>: <span class="math display">\begin{aligned}
A(x)B(x) &= (\sum_{i \ge 0}a_i x^i)(\sum_{j \ge 0}b_i x^i) \\
&= \sum_{i \ge 0}\sum_{j \ge 0} a_i b_j x^{i + j} \\
&= \sum_{n \ge 0}(\sum_{i = 0}^n a_i b_{n - i})x^n
\end{aligned}</span></p>
<p>If we multiply <span class="math inline">A(x)</span> by <span class="math inline">x^k</span>, what is <span class="math inline">[x^n]x^kA(x)</span>? <span class="math display">[x^n]x^kA(x) = \begin{cases}
[x^{n - k}]A(x), &n \ge k \\
0, &n < k
\end{cases}</span></p>
<p>Example: <span class="math inline">A(x) = (1 + 3x)^2</span>, <span class="math inline">B(x) = \sum_{i \ge 0}2^i x^i</span>.</p>
<blockquote>
<p><span class="math display">\begin{aligned}[x^n]A(x)B(x) &= [x^n](1 + 6x + 9x^2)B(x)\\ &= [x^n]B(x) + [x^n]6xB(x) + [x^n]9x^2B(x) \\ &= 25n^{n - 2}\end{aligned}</span> This is only valid for <span class="math inline">n \ge 2</span>, so we can manually calculate for <span class="math inline">n \le 1</span>.<br />
So <span class="math inline">A(x)B(x) = 1 + 8x + \sum_{n \ge 2} 25n^{n - 2}x^n</span>.</p>
</blockquote>
<p><strong>Inverse</strong>: The inverse of <span class="math inline">A(x)</span> is another series <span class="math inline">B(x)</span> such that <span class="math inline">A(x)B(x) = 1</span>.</p>
<p>Example: Find the inverse for <span class="math inline">1 - x</span>. Suppose <span class="math inline">\frac{1}{1 - x} = \sum_{n \ge 0} a_n x^n</span>. <span class="math display">\begin{aligned}
\frac{1}{1 - x}(1 - x) &= (\sum_{n \ge 0} a_n x_n)(1 - x) \\
1 &= a_0 + a_1x + a_2x^2 + ... - a_0x - a_1x^2 - a_2x^3 - ... \\
&= a_0 + \sum_{n \ge 1}(a_n - a_{n - 1}) x^n
\end{aligned}</span> Comparing coefficients, <span class="math inline">a_0 = 1</span>, <span class="math inline">a_i = a_{i + 1}</span> for <span class="math inline">i \ge 0</span>. So <span class="math inline">\frac{1}{1 - x} = \sum_{n \ge 0}x^n</span>.</p>
<blockquote>
<p>Some power series have <strong>no inverses</strong> …</p>
</blockquote>
<p>Example: <span class="math inline">\frac{1}{x}</span>. Suppose <span class="math inline">\frac{1}{x} = \sum_{n \ge 0} a_n x_n</span>. Then <span class="math inline">1 = \sum_{n \ge 0}a_n x^{n + 1}</span>. There is no constant on the right hand side so there is a contradiction. Therefore <span class="math inline">\frac{1}{x}</span> does not have an inverse.</p>
<p><strong>Theorem</strong>: <span class="math inline">A(x)</span> has an inverse if and only if <span class="math inline">[x^0]A(x) \not= 0</span>.</p>
<p>Example: Let <span class="math inline">A(x) = \frac{1 - x}{1 - 2x - 3x^2}</span>. Suppose <span class="math inline">A(x) = \sum_{n \ge 0}a_n x^n</span>.</p>
<blockquote>
<p><span class="math display">\begin{aligned} A(x) &= \frac{1 - x}{1 - 2x - 3x^2} \\ 1 - x &= A(x)(1 - 2x - 3x^2) \\ &= a_0 + (a_1 - 2a_0)x + \sum_{n \ge 2}(a_n - 2a_{n - 1} - 3a_{n - 2})x^n \end{aligned}</span> <strong>Comparing coefficients</strong>.<br />
<span class="math inline">1 = a_0</span>,<br />
<span class="math inline">-1 = a_1 - 2a_0 \Rightarrow a_1 = 1</span>,<br />
<span class="math inline">a_n = 2a_{n - 1} + 3a_{n - 2}</span>.</p>
<p>We can determine the coefficients of subsequent terms through the <em>recurrence</em>.</p>
</blockquote>
<h3 id="common-series">Common Series</h3>
<ol type="1">
<li><span class="math inline">\frac{1}{1 - x} = \sum_{n \ge 0} x^n</span>.</li>
<li><span class="math inline">\frac{1 - x^{k + 1}}{1 - x} = 1 + x + x^2 + ... + x^k</span>.</li>
<li><span class="math inline">(\frac{1}{1 - x})^k = \sum_{n \ge 0} {n + k - 1 \choose k - 1}x^n</span> (<em>negative binomial theorem</em>).
<ul>
<li>Proof: Induction on <span class="math inline">k</span>.</li>
</ul>
<blockquote>
<p><strong>Base Case</strong>: <span class="math inline">k = 1</span>, <span class="math inline">{n - 1 \choose 0} = 1</span>, <span class="math inline">\sum_{n \ge 0}x^n</span> is the geometric series. <strong>Induction Step</strong>: Consider <span class="math inline">k</span>. <span class="math display">\begin{aligned} (\frac{1}{1 - x})^k &= (\frac{1}{1 - x})(\frac{1}{1 - x})^{k - 1} \\ &= (1 + x + x^2 + ...)(\sum_{n \ge 0}{n - k + 2 \choose k - 2}x^n) \\ &= \sum_{n \ge 0}({n + k - 2 \choose k - 2} + {n + k - 3 \choose k - 2} + ... + {k - 2 \choose k - 2})x^n \\ &= \sum_{n \ge 0} {n + k - 1 \choose k - 1}x^n \end{aligned}</span></p>
</blockquote></li>
</ol>
<h3 id="composition-of-formal-power-series">Composition of Formal Power Series</h3>
<blockquote>
<p>Is <span class="math inline">A(B(x))</span> a formal power series?</p>
</blockquote>
<p>Example: <span class="math inline">G(x) = \frac{1}{1 - x}</span>, <span class="math inline">A(x) = \frac{x^2}{1 - x}</span>.</p>
<blockquote>
<p><span class="math display">\begin{aligned} G(A(x)) &= 1 + (\frac{x^2}{1 - x}) + (\frac{x^2}{1 - x})^2 + ... \\ &= \frac{1}{1 - \frac{x^2}{1 - x}} \\ &= \frac{1 - x}{1 - x - x^2} \end{aligned}</span></p>
</blockquote>
<p>Example: <span class="math inline">G(1 + x^2)</span>.</p>
<blockquote>
<p><span class="math inline">G(1 + x^2) = 1 + (1 + x^2) + (1 + x^2)^2 + ...</span>.<br />
Looking at the constant term, there it is not a well-defined, finite number, so <span class="math inline">G(1 + x^2)</span> is <strong>not</strong> a formal power series.</p>
</blockquote>
<p><strong>Theorem</strong>: If <span class="math inline">A(x)</span> and <span class="math inline">B(x)</span> are formal power series, where <span class="math inline">[x^0]B(x) = 0</span>, then <span class="math inline">A(B(x))</span> is a formal power series.</p>
<ul>
<li>Intuition is that we need a finite bound for the terms where <span class="math inline">[x^n]A(B(x))</span> can be found.</li>
</ul>
<h2 id="sum-and-product-lemmas">Sum and Product Lemmas</h2>
<h3 id="sum-lemma">Sum Lemma</h3>
<p>Let <span class="math inline">S = A \cup B</span>, <span class="math inline">A \cap B = \emptyset</span>. Let <span class="math inline">w</span> be the weight function on <span class="math inline">S</span>. Then <span class="math inline">\Phi_S(x) = \Phi_A(x) + \Phi_B(x)</span>.</p>
<blockquote>
<p><span class="math inline">\Phi_S(x) = \sum_{\rho \in S}x^{w(\rho)} = \sum_{\rho \in A} x^{w(\rho)} + \sum_{\rho \in B} x^{w(\rho)} = \Phi_A(x) + \Phi_B(x)</span>.</p>
</blockquote>
<h3 id="product-lemma">Product Lemma</h3>
<p>Let <span class="math inline">A</span>, <span class="math inline">B</span> be sets with weight functions <span class="math inline">\alpha, \beta</span>. Consider <span class="math inline">A \times B</span> with the weight function <span class="math inline">w(a, b) = \alpha(a) + \beta(b)</span>, for all <span class="math inline">(a, b) \in A \times B</span>. Then <span class="math inline">\Phi_{A \times B}(x) = \Phi_A(x)\Phi_B(x)</span>.</p>
<blockquote>
<p><span class="math display">\begin{aligned} \Phi_A(x)\Phi_B(x) &= (\sum_{a \in A}x^{\alpha(a)})(\sum_{b \in B}x^{\beta(b)}) \\ &= \sum_{a \in A}\sum_{b \in B}x^{w(a, b)} \\ &= \sum_{(a, b) \in A \times B}x^{w(a, b)} \\ &= \Phi_{A \times B}(x) \end{aligned}</span></p>
</blockquote>
<p>Example: How many ways can a sequence of <span class="math inline">k</span> non-negative integers sum up to <span class="math inline">n</span>?</p>
<blockquote>
<p>Define <span class="math inline">S = \mathbb{N}_0^k</span> (all sequences of <span class="math inline">k</span> non-negative integers). Define <span class="math inline">w(a_1, ..., a_k) = \sum_{i = 1}^k a_i</span>. Define <span class="math inline">\alpha(a) = a</span> for each copy of <span class="math inline">\mathbb{N}_0</span>. Then the produce lemma applies. <span class="math display">\begin{aligned}\Phi_S(x) &= (\Phi_{\mathbb{N}_0}(x))^k \\ &= \frac{1}{(1 - x)^k}\end{aligned}</span> Answer is <span class="math inline">[x^n]\frac{1}{(1 - x)^k} = {n + k - 1 \choose k - 1}</span>.</p>
</blockquote>
<h2 id="integer-composition-problems">Integer Composition Problems</h2>
<blockquote>
<p>A <span class="math inline">k</span>-tuple <span class="math inline">(a_1, ..., a_k)</span> of positive integers is a composition of <span class="math inline">n</span> if <span class="math inline">a_1 + ... + a_k = n</span>. Each <span class="math inline">a_i</span> is a part, and the composition has <span class="math inline">k</span> parts.</p>
</blockquote>
<p>Example: Compositions of <span class="math inline">n</span> with <span class="math inline">2k</span> parts. The first <span class="math inline">k</span> are at least <span class="math inline">5</span>, the last <span class="math inline">k</span> are multiples of <span class="math inline">3</span>.</p>
<blockquote>
<p>Define <span class="math inline">S = A^k \times B^k</span> where <span class="math inline">A = \{5, ... \}</span>, <span class="math inline">B = \{3, 6, 9, ...\}</span>. <span class="math inline">w(a_1, ..., a_k, b_1, ..., b_k) = a_1 + ... + a_k + b_1 + ... + b_k</span>. Use <span class="math inline">\alpha(a) = a</span> and <span class="math inline">\beta(b) = b</span>. <span class="math inline">\Phi_A(x) = \frac{x^5}{1 - x}</span>, <span class="math inline">\Phi_B(x) = \frac{x^3}{1 - x^3}</span>. By Product lemma, <span class="math inline">\Phi_S(x) = (\Phi_A(x))^k(\Phi_B(x))^k \frac{x^{8k}}{(1-x)^k(1-x^3)^k}</span>.</p>
<p>The answer is <span class="math inline">[x^{n-8k}](\frac{1}{1 - x})^k(\frac{1}{1 - x^3})^k</span>. We can reindex into <span class="math inline">\sum_{j = 0}^{\lfloor\frac{n - 8}{3}\rfloor}{k + n - 8k - 3j - 1 \choose k -1}{k + j - 1\choose k - 1}</span></p>
</blockquote>
<p>Example: How many compositions of <span class="math inline">n</span> are there?</p>
<blockquote>
<p>Define <span class="math inline">S = \mathbb{N}^0 \cup \mathbb{N} ... \ \cup_{k \ge 0}\mathbb{N}^k</span>. Define <span class="math inline">w</span> of a composition to be the sum of the parts. By sum lemma, <span class="math inline">\Phi_S(x) = \sum_{k \ge 0}(\Phi_{\mathbb{N}}(x))^k</span>. By product lemma, geometric series, and constant term is 0, <span class="math inline">\sum_{k \ge 0}(\frac{x}{1-x})^k = \frac{1}{1 - \frac{x}{1-x}} = \frac{1-x}{1-2x}</span>.</p>
<p>The answer is <span class="math inline">[x^n]\frac{1-x}{1-2x} = \begin{cases} 2^{n-1}, &n > 0 \\ 1, &n = 0\end{cases}</span></p>
</blockquote>
<p>Example: How many compositions of <span class="math inline">n</span> where each part is odd?</p>
<blockquote>
<p>Let <span class="math inline">\mathbb{N}_{odd} = \{1, 3, ...\}</span>. Define <span class="math inline">S = \cup_{k \ge 0}\mathbb{N}_{odd}^k</span>. We use the usual weight function. <span class="math display">\begin{aligned}\Phi_S(x) &= \sum_{k \ge 0}(\Phi_{\mathbb{N}_{odd}}(x))^k \\ &= \sum_{k \ge 0}(\frac{x}{1-x^2})^k \\ &= \frac{1}{1-\frac{x}{1-x^2}} \\ &= \frac{1-x^2}{1-x-x^2}\end{aligned}</span> Answer is <span class="math inline">[x^n]\frac{1-x^2}{1-x-x^2}</span>. Let <span class="math inline">A(x) = \frac{1-x^2}{1-x-x^2}</span>, <span class="math inline">A(x) - xA(x) - x^2A(x) = 1 - x^2</span>. By comparing coefficients, we have <span class="math inline">a_0 = 0, a_1 = 1, a_2 = 1, a_n = a_{n-1} + a_{n-2}</span>.</p>
</blockquote>
<p>We also have a combinatorial proof.</p>
<blockquote>
<p>Let <span class="math inline">S_n</span> be the set of all compositions of <span class="math inline">n</span> where every part is odd. We want a bijection <span class="math inline">f: S_n \to S_{n - 1} \cup S_{n-2}</span>. Define <span class="math inline">f(a_1, ... a_k) = \begin{cases}(a_1, ..., a_{k-1}), &a_k = 1 \\ (a_1, ..., a_k - 2), &a_k > 1\end{cases}</span>. We see that every part in the output is still valid (-2 does not change parity), so it is either in <span class="math inline">S_{n - 1}</span> or <span class="math inline">S_{n-2}</span>. The inverse is <span class="math inline">f^{-1}: S_{n-1} \cup S_{n-2} \to S_n</span> where <span class="math inline">f^{-1}(b_1, ..., b_l) = \begin{cases}(b_1, ..., b_l, 1), &\sum_{b_i} = n - 1 \\ (b_1, ..., b_l +2), &\sum_{b_i} = n - 2\end{cases}</span>.</p>
<p>So <span class="math inline">f</span> is a bijection and <span class="math inline">|S_n| = |S_{n-1}| + |S_{n-2}|</span></p>
</blockquote>
<h1 id="binary-strings">Binary Strings</h1>
<ul>
<li>Denote empty string <span class="math inline">\epsilon</span>.</li>
<li>A block is a maximal non-empty substring of all 0’s or all 1’s.</li>
</ul>
<p>The general question given is how many binary strings of length <span class="math inline">n</span> have certain properties.</p>
<ol type="1">
<li>Find an expression for the set of all binary strings with these properties.</li>
<li>Define the weight of a string to be its length.</li>
<li>Find the generating series of <span class="math inline">S</span> with respect to <span class="math inline">w</span>.</li>
<li>Answer is <span class="math inline">[x^n]\Phi_S(x)</span>.</li>
</ol>
<h2 id="operations-on-sets-of-strings">Operations on Sets of Strings</h2>
<ol type="1">
<li>Concatenation of two strings <span class="math inline">A, B</span>. <span class="math inline">AB = \{ab | a \in A, b \in B\}</span>.</li>
<li>Star. <span class="math inline">A^* = \cup_{k \ge 0} A^k</span>, <span class="math inline">A^0 = \{\epsilon\}</span>, <span class="math inline">\{0, 1\}^*</span> is the set of all binary strings.</li>
</ol>
<p>We want to be able to apply product and sum lemma to string operations, but we need to ensure that they are not ambiguous.</p>
<h3 id="ambiguity">Ambiguity</h3>
<blockquote>
<p>Strings that can be generating in multiple ways.</p>
</blockquote>
<p><span class="math inline">AB</span> is ambiguous if <span class="math inline">\exists</span> <span class="math inline">s \in AB, s = a_1 b_1 = a_2 b_2</span> for distinct <span class="math inline">a_1, a_2 \in A</span>, <span class="math inline">b_1, b_2 \in B</span>. <span class="math inline">A \cup B</span> is ambiguous if <span class="math inline">A \cap B \neq \emptyset</span>.</p>
<p><strong>Theorem</strong>: Let <span class="math inline">A, B</span> be sets of strings.</p>
<ol type="1">
<li>If <span class="math inline">A \cup B</span> is unambiguous, then <span class="math inline">\Phi_{A \cup B}(x) = \Phi_A(x) + \Phi_B(x)</span>.</li>
<li>If <span class="math inline">AB</span> is unambiguous, then <span class="math inline">\Phi_{AB}(x) = \Phi_A(x)\Phi_B(x)</span>.</li>
<li><p>If <span class="math inline">A^*</span> is unambiguous, then <span class="math inline">\Phi_{A^*}(x) = \frac{1}{1 = \Phi_A(x)}</span>.</p>
<blockquote>
<p>By 1 and 2, the sum and product lemma apply. <span class="math inline">\Phi_{A^*}(x) = \sum_{k \ge 0}(\Phi_A(x))^k</span> by geometric series and <span class="math inline">[x^0]\Phi_A(x) = 0</span> (<span class="math inline">\epsilon</span> would make <span class="math inline">A^*</span> ambiguous).</p>
</blockquote></li>
</ol>
<h3 id="unambiguous-expressions-for-strings">Unambiguous Expressions for Strings</h3>
<ol type="1">
<li><span class="math inline">\{0, 1\}^*</span>.</li>
<li><span class="math inline">\{0\}^*(\{1\}\{0\}^*)^*</span>, or flip all the bits.</li>
<li><strong>Block decomposition</strong>: <span class="math inline">\{0\}^*(\{1\}\{1\}^*\{0\}\{0\}^*)^*\{1\}^*</span>, or flip all the bits.</li>
</ol>
<p>For string generation problems, start with one of the three unambiguous expressions and then remove parts that violate our conditions.</p>
<p>Example: The set of all strings with no three consecutive 0’s.</p>
<blockquote>
<p>Start with <span class="math inline">\{0\}^*(\{1\}\{0\}^*)^*</span>, we can find 000 in both instances of <span class="math inline">\{0\}^*</span>. Remove these instances <span class="math inline">\{0\}^* \to \{\epsilon, 0, 00\}</span>. We are left with <span class="math inline">\{\epsilon, 0, 00\}(\{1\}\{\epsilon, 0, 00\})^*</span>.</p>
</blockquote>
<p>Example: Set of all strings where an even block of 0’s cannot be followed by an odd block of 1’s.</p>
<blockquote>
<p>We start with block decomposition and break into cases with even and odd block of 0’s. In the odd case, we can leave the 1’s alone but in the even case, we need to ensure an even block of 1’s. We are left with <span class="math inline">\{1\}^*(\{00\}\{00\}^*\{11\}\{11\}^* \cup \{0\}\{00\}^*\{1\}\{1\}^*)^* \{0\}^*</span>.</p>
</blockquote>
<h2 id="string-recursion">String Recursion</h2>
<p>Let <span class="math inline">S</span> be the set of all strings, we can recursively define <span class="math inline">S</span> as <span class="math inline">S = \{0, 1\}S \cup \{\epsilon\}</span>. We get a generating series expression <span class="math inline">\Phi_S(x) = 2x\Phi_S(x) + 1</span>, <span class="math inline">\Phi_S(x) = \frac{1}{1 - 2x}</span>.</p>
<p>Example: Sets that do not have 1010 as a substring</p>
<blockquote>
<p>Let <span class="math inline">T</span> be a string with one copy of 1010, which is at the right end of the string.</p>
<p>We have two equations.</p>
<ol type="1">
<li><span class="math inline">\{\epsilon\} \cup S\{0, 1\} = S \cup T</span>.
<ul>
<li>(<span class="math inline">\subseteq</span>): <span class="math inline">\epsilon \in S</span>. Let <span class="math inline">\sigma \in S</span>. Then <span class="math inline">\sigma\{0, 1\}</span> has no 1010 unless <span class="math inline">\sigma</span> ends with 101 and we attach a 0 at the end. If so, this would be the only copy of 1010 in <span class="math inline">\sigma 0</span> as no 1010 can be found in <span class="math inline">\sigma</span>. So <span class="math inline">\sigma 0</span> and <span class="math inline">\sigma 1</span> are in <span class="math inline">S \cup T</span>.</li>
<li>(<span class="math inline">\supseteq</span>): A string in <span class="math inline">S</span> is either empty, or we can take off the rightmost bit and obtain another string in <span class="math inline">S</span>. <span class="math inline">S \subseteq \{\epsilon\} \cup S\{0, 1\}</span>. For a string in <span class="math inline">T</span>, removing the rightmost bit destroys the only copy of 1010 in the string. So <span class="math inline">T \subseteq S\{0\}</span>. So <span class="math inline">S \cup T \subseteq \{\epsilon\} \cup S\{0, 1\}</span>.</li>
</ul></li>
<li><span class="math inline">S\{1010\} = T \cup T\{10\}</span>.
<ul>
<li>(<span class="math inline">\subseteq</span>): Let <span class="math inline">\sigma \in S</span>. Then <span class="math inline">\sigma 1010</span> has at least 1 copy of 1010 at the right end. If that is the only copy then <span class="math inline">\sigma \{1010\} \in T</span>. A second copy can exist if <span class="math inline">\sigma</span> ends with 10, so <span class="math inline">\sigma 1010</span> ends with 101010. Then this is in <span class="math inline">T\{10\}</span>.</li>
<li>(<span class="math inline">\supseteq</span>): Any string in <span class="math inline">T</span> ends with 1010. Removing this destroys all copies of 1010 in the string, so it is in <span class="math inline">S\{1010\}</span>.</li>
</ul></li>
</ol>
<p>We can solve for <span class="math inline">\Phi_S(x)</span> using the two equations, and obtain <span class="math inline">\Phi_S(x) = \frac{1+x^2}{1-2x+x^2-2x^3+x^4}</span>.</p>
</blockquote>
<h1 id="coefficients-in-rational-expressions">Coefficients in Rational Expressions</h1>
<blockquote>
<p>Finding <span class="math inline">[x^n]\frac{f(x)}{g(x)}</span>.</p>
</blockquote>
<p>Example: <span class="math inline">A(x) = \sum_{n \ge 0}a_n x^n</span> where <span class="math inline">A(x) = \frac{3-8x-2x^2}{1-7x+16x^2-12x^3}</span>.</p>
<blockquote>
<p>We can use partial fraction decomposition to see that <span class="math inline">A(x) = \frac{-1}{1-2x} + \frac{3}{(1-2x)^2} + \frac{1}{1-3x}</span>. This allows us to solve for <span class="math inline">[x^n]A(x)</span>. <span class="math display">\begin{aligned}[x^n]A(x) &= [x^n] \frac{-1}{1-2x} + [x^n]\frac{3}{(1-2x)^2} + [x^n]\frac{1}{1-3x} \\ &= -1(2^n) + 3{n + 1 \choose 1}2^n + 3^n \\ &= -(2^n) + 3(n+1)2^n + 3^n\end{aligned}</span></p>
</blockquote>
<p>Let us generalize this approach.</p>
<p>Suppose <span class="math inline">A(x) = \frac{f(x)}{g(x)}</span>. If <span class="math inline">deg(f(x)) \ge deg(g(x))</span>, we can use polynomial long division to get <span class="math inline">A(x) = q(x) + \frac{r(x)}{g(x)}</span> where <span class="math inline">deg(r(x)) < deg(g(x))</span>.</p>
<p>Assume constant term of <span class="math inline">g(x) = 1</span> (if 0, then we cannot divide). Then we can factor <span class="math inline">g(x) = (1-r_1 x)^{e_1}(1 - r_2 x)^{e_2} ...(1-r_k x)^{e_k}</span> by the fundamental theorem of algebra. Using partial fraction decomposition, we can obtain <span class="math inline">A(x) = \frac{p_1(x)}{(1-r_1 x)^{e_1}} + ... + \frac{p_k(x)}{(1-r_k x)^{e_k}}</span>, where <span class="math inline">deg(p_i(x)) < e_i</span>.</p>
<p>Each <span class="math inline">\frac{p_i(x)}{(1-r_i)^{e_i}} = \frac{c_1}{1-r_1 x} + ... + \frac{c_{e_i}}{(1-r_i x)^{e_i}}</span>, <span class="math inline">c_j</span> constant.</p>
<p><span class="math display">\begin{aligned}[x^n]\frac{p_i(x)}{(1-r_i)^{e_i}} &= [x^n]\frac{c_1}{1-r_1 x} + ... + [x^n]\frac{c_{e_i}}{(1-r_i x)^{e_i}} \\ &= \sum_{j = 1}^{e_i} [x^n]\frac{c_j}{(1-r_i x)^j} \\ &= \sum_{j=1}^{e_i} c_j{n + j - 1 \choose j - 1}r_i^n \\ &= \sum_{j = 1}^{e_i} c_j \frac{(n + j - 1)!}{(j - 1)!(n)!}r_i^n \\ &= \sum_{j = 1}^{e_i} Q(n)r_i^n\end{aligned}</span> Where <span class="math inline">Q(n)</span> is a polynomial of <span class="math inline">n</span> of degree at most <span class="math inline">j - 1</span>.</p>
<p>So <span class="math inline">[x^n]\frac{p_i(x)}{(1-r_i x)^{e_i}} = Q_i(n)r_i^n</span>, where <span class="math inline">Q_i(n)</span> is a polynomial in <span class="math inline">n</span> of degree at most <span class="math inline">e_i - 1</span>. So <span class="math inline">[x^n]A(x) = Q_1(n)r_1^n + ... + Q_k(n)r_k^n</span>, where <span class="math inline">Q_i(n)</span> has degree at most <span class="math inline">e_i - 1</span>.</p>
<p><strong>Characteristic Polynomial</strong>: If <span class="math inline">g(x) = (1-r_1x)^e_i ... (1-r_kx)^{e_k}</span>, then its characteristic polynomial is <span class="math inline">g^*(x) = (x-r_1)^{e_i} ... (x-r_x)^{e_k}</span>. Then <span class="math inline">r_1, ..., r_k</span> are the roots of the characteristic polynomial with multiplicities <span class="math inline">e_1, ..., e_k</span>.</p>
<p>Example: <span class="math inline">\{a_n\}</span> satisfies <span class="math inline">a_0 = 1, a_5 = 5</span> and <span class="math inline">a_n - 5a_{n - 1} + 6a_{n-2} = 0</span> for <span class="math inline">n \ge 2</span>.</p>
<blockquote>
<p>First find <span class="math inline">A(x) = \sum_{n \ge 0}x^n</span> as a rational expression.<br />
For each <span class="math inline">n \ge 2</span> multiply its recurrence by <span class="math inline">x^n</span>. <span class="math display">\begin{aligned}a_2x^2 - 5a_1x^2 + 6a_0x^2 &= 0 \\ a_3x^3 - 5a_2x^3 + 6a1x^3 &= 0 \\ ... \\ a_nx^n - 5a_{n-1}x^n + 6a_{n-2}x^n &= 0\end{aligned}</span> Add all of the equations together. <span class="math display">\begin{aligned}\sum_{n \ge 2}a_nx^n - 5\sum_{n \ge 1}a_nx^{n+1} + 6\sum_{n \ge 0}a_nx^{n+2} &= 0 \\ \sum_{n \ge 2}a_nx^n - 5x\sum_{n \ge 1}a_nx^n + 6x^2\sum_{n \ge 0}a_nx^n &= 0 \\ (A(x) - a_0 - a_1x) - 5x(A(x) - a_0) + 6x^2A(x) &= 0\end{aligned}</span> We have <span class="math inline">A(x)(1 - 5x + 6x^2) - 1 - 5x + 5x = 0</span> and <span class="math inline">A(x) = \frac{1}{1 - 5x + 6x^2}</span>. The characteristic polynomial is <span class="math inline">x^2 - 5x + 6 = (x-2)(x-3)</span>. The roots are <span class="math inline">x=2,3</span> with multiplicity 1 each.</p>
<p>The answer is <span class="math inline">[x^n]A(x) = a_n = A\cdot 2^n + B \cdot 3^n</span> for constants <span class="math inline">A, B</span>.<br />
For <span class="math inline">a_0</span>: <span class="math inline">1 = A + B</span>.<br />
For <span class="math inline">a_1</span>: <span class="math inline">5 = 2A + 3B</span>.<br />
We have <span class="math inline">A = -2</span>, <span class="math inline">B = 3</span>, so <span class="math inline">a_n = (-2)2^n + (3)3^n</span>.</p>
</blockquote>
<p>We see that there is a shortcut from the recurrence to the characteristic polynomial. If <span class="math inline">\{a_n\}</span> satisfies the recurrence <span class="math inline">a_n + c_1a_{n - 1} + ... + c_ka_{n - k} = 0</span>, then its corresponding characteristic polynomial is <span class="math inline">x^k + c_1x^{k-1} + ... + c_k</span>. <span class="math inline">A(x) = \sum a_nx^n</span> has the form <span class="math inline">A(x) = \frac{...}{1 + c_1x + ... + c_kx^k}</span>.</p>
<p>Example: <span class="math inline">\{a_n\}</span> satisfies <span class="math inline">a_0 = 1, a_1, = 2, a_2 = 1</span> where <span class="math inline">a_n - 3a_{n-1} + 3a_{n-2} - a_{n-3} = 0</span> for <span class="math inline">n \ge 3</span>.</p>
<blockquote>
<p>The characteristic polynomial is <span class="math inline">x^3 - 3x^2 + 3x - 1 = (x-1)^3</span>. The root is <span class="math inline">x=1</span> with multiplicity 3. We have <span class="math inline">a_n = An^2 + Bn + C</span> for some constants <span class="math inline">A, B, C</span>.<br />
For <span class="math inline">a_0</span>: <span class="math inline">1 = C</span>.<br />
For <span class="math inline">a_1</span>: <span class="math inline">2 = A + B + C</span>.<br />
For <span class="math inline">a_2</span>: <span class="math inline">1 = 4A + 2B + C</span>.<br />
We have <span class="math inline">A = -1, B = 2, C = 1</span>, so <span class="math inline">a_n = (-1)n^2 + 2n + 1</span>.</p>
</blockquote>
<p>Example: <span class="math inline">a_0 = 7, a_1 = 10, a_2 = 13, a_n - 7a_{n-1} + 15a_{n-2}-9a_{n-3}=0</span> for <span class="math inline">n \ge 3</span>.</p>
<blockquote>
<p>The characteristic polynomial is <span class="math inline">x^3 - 7x^2 + 15x - 9 = (x-3)^2(x-1)</span>. The roots are <span class="math inline">x=3,1</span> with multiplicities <span class="math inline">2</span> and <span class="math inline">1</span> respectively. We have <span class="math inline">a_n = (An + B)3^n + C</span> for constants <span class="math inline">A, B, C</span>.<br />
For <span class="math inline">a_0</span>: <span class="math inline">7 = B + C</span>.<br />
For <span class="math inline">a_1</span>: <span class="math inline">10 = 3A + 3B + C</span>.<br />
For <span class="math inline">a_1</span>: <span class="math inline">13 = 18A + 9B + C</span>.<br />
We have <span class="math inline">A = -1, B = 3, C = 4</span>, so <span class="math inline">a_n = (-n + 3)3^n + 4</span>.</p>
</blockquote>
<p>Example: <span class="math inline">f_0 = 0, f_1 = 1, f_n - f_{n - 1} - f_{n - 2} = 0</span>, <span class="math inline">n \ge 2</span>.</p>
<blockquote>
<p>Characteristic polynomial is <span class="math inline">x^2 - x - 1</span>. The roots are <span class="math inline">x = \frac{1 \pm \sqrt 5}{2}</span>, so <span class="math inline">f_n = A(\frac{1+\sqrt 5}{2})^n + B(\frac{1-\sqrt 5}{2})^n</span> for constants <span class="math inline">A, B</span>.<br />
For <span class="math inline">f_0</span>: <span class="math inline">0 = A + B</span>.<br />
For <span class="math inline">f_1</span>: <span class="math inline">1 = (\frac{1+\sqrt 5}{2})A + (\frac{1 - \sqrt 5}{2})B</span>.<br />
We have <span class="math inline">A = \frac{1}{\sqrt 5}</span>, <span class="math inline">B = \frac{-1}{\sqrt 5}</span>, so <span class="math inline">f_n = \frac{(\frac{1 + \sqrt 5}{2})^n - (\frac{1-\sqrt 5}{2})^n}{\sqrt 5}</span>. We can show that <span class="math inline">f_n \in \mathbb{Z}</span>.</p>
</blockquote>
<h1 id="graph-theory">Graph Theory</h1>
<p>A graph <span class="math inline">G</span> is a pair <span class="math inline">(V(G), E(G))</span> where <span class="math inline">V(G)</span> is a set of objects called vertices, and <span class="math inline">E(G)</span> is a set of unordered pairs of <span class="math inline">V(G)</span> called edges. We might say <span class="math inline">G = (V, E)</span>.</p>
<p><strong>Terminology</strong>:</p>
<ol type="1">
<li>Two vertices <span class="math inline">u, v</span> are adjacent if <span class="math inline">\{u, v\}</span> is an edge. They are also said to be neighbours.</li>
<li>The set of all neighbours of <span class="math inline">v</span> in <span class="math inline">G</span> is its neighbourhood, denoted <span class="math inline">N_G(v)</span>.</li>
<li>Edge <span class="math inline">e = \{u, v\}</span> is <strong>incident</strong> with its end points <span class="math inline">u, v</span>. We can also say that <span class="math inline">e</span> <strong>joins</strong> <span class="math inline">u</span> and <span class="math inline">v</span>.</li>
</ol>
<p><strong>Notes</strong>:</p>
<ol type="1">
<li><span class="math inline">e=uv</span> abbreviates $ = {u, v}$.</li>
<li><span class="math inline">uv = vu</span>, edges are unordered.</li>
<li>For most of this course, our graphs are “simple”. There are no loops or multiple edges.</li>
<li>Graphs are considered to be finite.</li>
</ol>
<h2 id="degrees">Degrees</h2>
<p>Degree of vertex <span class="math inline">v</span> in <span class="math inline">G</span> is the number of edges in <span class="math inline">G</span> that are incident with <span class="math inline">v</span>, denoted <span class="math inline">deg_G(v)</span> or <span class="math inline">deg(v)</span>.</p>
<p><span class="math inline">\sum_{v \in V(G)} deg(v)</span> is always even.</p>
<blockquote>
<p><strong>Handshaking Lemma</strong>: For any graph <span class="math inline">G</span>, <span class="math inline">\sum_{v \in V(G)}deg(v) = 2|E(G)|</span>.</p>
<p>Each <span class="math inline">e = uv \in E(G)</span> contributes 2 to the sum, one for <span class="math inline">dev(u)</span> and one for <span class="math inline">deg(v)</span>.</p>
</blockquote>
<p><strong>Corollary</strong>: For any graph <span class="math inline">G</span>, the number of odd degree vertices is even.</p>
<blockquote>
<p><span class="math inline">O, E \in V(G)</span> with odd, even vertices respectively. Then <span class="math inline">\sum_{v \in V(G)}deg(V) = \sum_{v \in O}deg(v) + \sum_{v \in E}deg(v)</span>. By handshaking lemma, <span class="math inline">\sum_{v \in V(G)}deg(v)</span> is even. <span class="math inline">\sum_{v \in E}deg(v)</span> is even because it is a sum of even numbers. Therefore, <span class="math inline">\sum_{v \in O}deg(v)</span> is even. A sum of odd integers is even, so there are an even number of them.</p>
</blockquote>
<h2 id="isomorphism">Isomorphism</h2>
<p><strong>Definition</strong>: Two graphs <span class="math inline">G_1</span>, <span class="math inline">G_2</span> are <strong>isomorphic</strong> if there exists a bijection <span class="math inline">f: V(G_1) \to V(G_2)</span> such that <span class="math inline">uv \in E(G_1)</span> if and only if <span class="math inline">f(u)f(v) \in E(G_2)</span> (edge adjacency is preserved). Such a function is an <strong>isomorphism</strong>.</p>
<p>Assume <span class="math inline">|E(G_1)| \neq |E(G_2)|</span>, then there cannot possibly be a bijection between <span class="math inline">V(G_1)</span> and <span class="math inline">V(G_2)</span>. Similarly, we can look at the degree of certain vertices.</p>
<p>To prove that two graphs are isomorphic, find an isomorphism. To prove that two graphs are not isomorphic, find an adjacency structure that exists in one but not the other.</p>
<h2 id="classes-of-graphs">Classes of Graphs</h2>
<ol type="1">
<li><strong>Complete graph</strong>: a graph where every pair of vertices is an edge. A complete graph on <span class="math inline">n</span> vertices is <span class="math inline">K_n</span>. There are <span class="math inline">n \choose 2</span> edges in <span class="math inline">K_n</span>.</li>
<li><p><strong>K-Regular</strong>: a graph where every vertex has degree <span class="math inline">k</span>. In a <span class="math inline">k</span>-regular graph of <span class="math inline">n</span> vertices, there are <span class="math inline">\frac{nk}{2}</span> edges.</p>
<blockquote>
<p>By handshaking lemma, <span class="math inline">2|E(G)| = \sum_{v \in V(G)}deg(v) = \sum_{v \in V(G)}k = nk</span>.</p>
</blockquote></li>
<li><p>G is <strong>bipartite</strong> if there exists a partition <span class="math inline">(A, B)</span> of <span class="math inline">V(G)</span> such that every edge in <span class="math inline">G</span> joins one vertex in <span class="math inline">A</span> with one vertex in <span class="math inline">B</span>.</p>
<ul>
<li><p>Cycles with an odd number of vertices are not bipartite.</p></li>
<li><p>For <span class="math inline">m, n \ge 1</span>, the <strong>complete bipartite graph</strong> <span class="math inline">K_{m,n}</span> has bipartition <span class="math inline">(A, B)</span>, <span class="math inline">|A| = m</span>, <span class="math inline">|B| = n</span>, and each vertex in <span class="math inline">A</span> is adjacent to all vertices in <span class="math inline">B</span>. <span class="math inline">|E(K_{m,n})| = mn</span>.</p></li>
</ul></li>
</ol>
<h2 id="n-cube">N-Cube</h2>
<p><strong>Definition</strong>: The <strong>n-cube</strong> is the graph where the vertex set consists of all binary strings of length <span class="math inline">n</span>, and two strings are adjacent if and only if they differ by exactly one bit.</p>
<h3 id="n-cube-properties">N-Cube Properties</h3>
<ol type="1">
<li><span class="math inline">2^n</span> vertices.</li>
<li><span class="math inline">n</span>-regular. For any string <span class="math inline">s</span>, it has <span class="math inline">n</span> bits. Changing 1 of them gives a neighbour of <span class="math inline">s</span>. So <span class="math inline">s</span> has <span class="math inline">n</span> neighbours.</li>
<li><span class="math inline">n2^{n-1}</span> edges. Total degree is <span class="math inline">n2^n</span>. By Handshaking Lemma, the number of edges is half.</li>
<li>Bipartite. Let <span class="math inline">A</span> be a binary string of length <span class="math inline">n</span> with an even number of 1’s, and <span class="math inline">B</span> be the binary string of length <span class="math inline">n</span> with an odd number of 1’s. Suppose <span class="math inline">st</span> is an edge in the n-cube. We obtain <span class="math inline">t</span> from <span class="math inline">s</span> by either changing <span class="math inline">0 \to 1</span> or <span class="math inline">1 \to 0</span>. The parities of <span class="math inline">s</span> and <span class="math inline">t</span> are different, so <span class="math inline">st</span> joins <span class="math inline">A</span> to <span class="math inline">B</span>.</li>
</ol>
<h3 id="recursive-construction">Recursive Construction</h3>
<ol type="1">
<li>Take 2 copies of the n-cube.</li>
<li>Insert 1 into the front of all strings in one copy, and insert 0 in the other copy.</li>
<li>Join the 1’s to 0’s for any <span class="math inline">s</span> in the n-cube.</li>
</ol>
<h2 id="walks-and-paths">Walks and Paths</h2>
<p>Define a <strong>u,v-walk</strong> as a sequence of alternating vertices and edges <span class="math inline">u=v_0, e_1, v_1, e_2, ..., e_k, v_k = v</span> where <span class="math inline">e_i = v_{i-1}v_i</span> for each <span class="math inline">i</span>. This walk has <strong>length</strong> <span class="math inline">k</span> (the number of edges used, including repetition). It is a <strong>closed</strong> walk if <span class="math inline">u=v</span>.</p>
<ul>
<li>We can uniquely define a walk by the sequence of vertices in simple graphs.</li>
</ul>
<p>Define a <strong>u,v-path</strong> as a u,v-walk with no repeated vertices or edges. A <strong>trivial</strong> path / walk is one with length 0.</p>
<p><strong>Proposition</strong>: If there is a u,v-walk, then there is a u,v-path.</p>
<blockquote>
<p>Among all u,v-walks, let <span class="math inline">W</span> be one with the shortest length (Well-ordering Principle). If <span class="math inline">W</span> has no repeated vertices, then <span class="math inline">W</span> is a u,v-path and we are done. Suppose <span class="math inline">x</span> is used at least twice. Then we can decompose <span class="math inline">W</span> into <span class="math inline">W = u,W_1, x, W_2,x, W_3, v</span> where <span class="math inline">W_i</span> are walks in <span class="math inline">W</span>. Then <span class="math inline">u, W_1, x, W_3, v</span> is a u,v-walk which is shorter than <span class="math inline">W</span> since <span class="math inline">W_2</span> must be non-trivial.</p>
</blockquote>
<p><strong>Corollary</strong>: If there is a u,v-path and a v,w-path, then there is a u,w-path. <strong>Transitivity</strong> property.</p>
<blockquote>
<p>A u,v-path followed by a v,w-path is a u,w-walk. By the proposition above, there exists a u,w-path.</p>
</blockquote>
<p>This is also <strong>reflexive</strong> and <strong>symmetric</strong>. Therefore, it is an <strong>equivalence</strong> relation.</p>
<h2 id="cycles">Cycles</h2>
<p>We define a <strong>cycle</strong> as a nontrivial closed walk, with no repeated vertices or edges. Cycles have length of at least 3, have an equal number of vertices and edges and are 2-regular.</p>
<p><strong>Theorem</strong>: If every vertex of <span class="math inline">G</span> has degree at least 2, then <span class="math inline">G</span> contains a cycle. The converse is not true.</p>
<blockquote>
<p>Let <span class="math inline">v_0, v_1, ..., v_k</span> be a longest path in <span class="math inline">G</span> (such a path exists since every path uses at most <span class="math inline">|V(G)|</span> vertices). Vertex <span class="math inline">v_0</span> has a neighbour <span class="math inline">v_1</span>, but <span class="math inline">v_0</span> has a degree at least 2, so it has at least one other neighbour, say <span class="math inline">x</span>. If <span class="math inline">x</span> is not on the path, then the path <span class="math inline">x, v_0, ..., v_k</span> is longer than our longest path, which is a contradiction. So <span class="math inline">x = v_i</span> for some <span class="math inline">2 \le i \le k</span>, and <span class="math inline">v_0, v_1, ..., v_i, v_0</span> is a cycle in <span class="math inline">G</span>.</p>
</blockquote>
<h2 id="connectivity">Connectivity</h2>
<p><strong>Definition</strong>: <span class="math inline">G</span> is <strong>connected</strong> if there is a u,v-path for every pair of vertices <span class="math inline">u, v\in V(G)</span>.</p>
<p><strong>Theorem</strong>: If there exists a vertex <span class="math inline">u</span> such that a u,v-path exists for any <span class="math inline">v \in V(G)</span>, then <span class="math inline">G</span> is connected.</p>
<blockquote>
<p>Let <span class="math inline">x, y \in V(G)</span>. We are given that there exists an x,u-path and a u,y-path. Together they form a x,y-walk which means there exists an x,y-path. Since our choice of <span class="math inline">x, y</span> is arbitrary, <span class="math inline">G</span> is connected.</p>
</blockquote>
<p><strong>Theorem</strong>: The n-cube is connected.</p>
<blockquote>
<p>Let <span class="math inline">v_0</span> be the string of <span class="math inline">n</span> 0’s, let <span class="math inline">x</span> be any binary string of length <span class="math inline">n</span>. Suppose <span class="math inline">x</span> has <span class="math inline">k</span> 1’s, located at positions, <span class="math inline">i_1, ..., i_k</span>. Define <span class="math inline">k</span> strings <span class="math inline">v_1, ..., v_k</span> as follows. <span class="math inline">v_j</span> is a string of length <span class="math inline">n</span> with exactly <span class="math inline">j</span> 1’s positions <span class="math inline">i_1, ..., i_j</span>. Then <span class="math inline">V_j, V_{j+1}</span> differ in exactly one bit, at position <span class="math inline">i_{j+1}</span> for <span class="math inline">j = 0, ..., k - 1</span>. So they are adjacent in the n-cube. Then <span class="math inline">v_0, v_1, ..., v_k=x</span> is a <span class="math inline">v_0, x</span>-path. Therefore the n-cube is connected.</p>
</blockquote>
<h2 id="components-and-cut">Components and Cut</h2>
<p><strong>Definition</strong>: A <strong>subgraph</strong> <span class="math inline">H</span> of <span class="math inline">G</span> has vertex set <span class="math inline">V(H) \subseteq V(G)</span> and edge set <span class="math inline">E(H) \subseteq E(G)</span> where each in edge in <span class="math inline">E(H)</span> joins 2 vertices in <span class="math inline">V(H)</span>. If <span class="math inline">|V(H)| = |V(G)|</span>, it is a <strong>spanning subgraph</strong>.</p>
<p>Define a <strong>component</strong> of <span class="math inline">G</span> as a maximal connected nonempty subgraph of <span class="math inline">G</span>.</p>
<ul>
<li>A connected graph has exactly 1 component and a disconnected graph has at least 2 components.</li>
<li>There is no edge joining a vertices from different components (if such an edge existed, our components would not be maximal).</li>
</ul>
<p>Let <span class="math inline">X \subseteq V(G)</span>. The <strong>cut induced by X</strong> is the set of all endpoints with exactly one endpoint in <span class="math inline">X</span>.</p>
<ul>
<li>The cut induced by a <strong>component</strong> is empty.</li>
<li>If there is an empty cut, then is the graph is not connected? False, <span class="math inline">X = \emptyset, V(G)</span>.</li>
</ul>
<p><strong>Theorem</strong>: <span class="math inline">G</span> is not connected if and only if there exists a non-empty proper subset <span class="math inline">X</span> of <span class="math inline">V(G)</span> such that the cut induced by <span class="math inline">X</span> is empty.</p>
<blockquote>
<p>(<span class="math inline">\Rightarrow</span>) If <span class="math inline">G</span> is not connected, then <span class="math inline">G</span> has at least 2 components. Let <span class="math inline">H</span> be one of them. The set <span class="math inline">V(H)</span> is non-empty since <span class="math inline">H</span> is a component, and it is a proper subset of <span class="math inline">V(G)</span> since there is at least one other component. By previous observation, the cut induced by <span class="math inline">V(H)</span> is empty.</p>
<p>(<span class="math inline">\Leftarrow</span>) Suppose <span class="math inline">X</span> is a non-empty proper subset of <span class="math inline">V(G)</span> that induces an empty cut. Let <span class="math inline">u \in X, v \notin X</span>. These vertices exist since <span class="math inline">X</span> is a non-empty proper subset. Assume there exist a u,v-path, say <span class="math inline">u=w_1,w_2,...,w_k=v</span>. Let <span class="math inline">i</span> be the largest index such that <span class="math inline">w_i \in X</span>. Such <span class="math inline">i</span> exists since <span class="math inline">w_1 \in X</span> and <span class="math inline">i < k</span> since <span class="math inline">w_k \notin X</span>. So <span class="math inline">w_{i+1} \notin X</span>. Therefore <span class="math inline">w_i w_{i+1}</span> is in the cut induced by <span class="math inline">X</span>, which is a contradiction. So no u,v-path exists, so <span class="math inline">G</span> is not connected.</p>
</blockquote>
<p>Example: Let <span class="math inline">G_n</span> be the graph with all binary strings of length <span class="math inline">n</span> as vertices, and two strings are adjacent if and only if they differ in exactly 2 bits. We claim that <span class="math inline">G_n</span> is not connected.</p>
<blockquote>
<p>Let <span class="math inline">X</span> be all binary strings of length <span class="math inline">n</span> with even number of 1’s. This is a non-empty proper subset <span class="math inline">0..0 \in X</span> and <span class="math inline">1..0 \notin X</span>. Suppose <span class="math inline">st</span> is an edge where <span class="math inline">s \in X</span>. <span class="math inline">s</span> has an even number of 1’s. By changing 2 bits, <span class="math inline">t</span> also has an even number of 1’s. <span class="math inline">t \in X</span>, so no edge joins <span class="math inline">X</span> with <span class="math inline">V(G) \setminus X</span>. So the cut induced by <span class="math inline">X</span> is empty, and <span class="math inline">G_n</span> is not connected.</p>
</blockquote>
<h1 id="eulerian-circuits">Eulerian Circuits</h1>
<blockquote>
<p>An <strong>Eulerian Circuit</strong> is a closed walk that uses every edge of the graph exactly once.</p>
</blockquote>
<h2 id="properties-of-eulerian-circuits">Properties of Eulerian Circuits</h2>
<p>Suppose <span class="math inline">G</span> has an Eulerian circuit.</p>
<p>Which graphs have Eulerian circuits?</p>
<p><strong>Theorem</strong>: Let <span class="math inline">G</span> be a connected graph. Then <span class="math inline">G</span> has an Eulerian circuit if and only if every vertex of <span class="math inline">G</span> has even degree.</p>
<blockquote>
<p>(<span class="math inline">\Rightarrow</span>) Assume <span class="math inline">G</span> is connected. Each time we visit a vertex, we need to use 2 distinct edges, one to get in, and one to get out. So the degree of each vertex is even.</p>
<p>(<span class="math inline">\Leftarrow</span>) We prove by induction on the number of edges of <span class="math inline">G</span>, <span class="math inline">m</span>.</p>
<p><strong>Base Case</strong>: When <span class="math inline">G</span> has 0 edges, it has a trivial Eulerian circuit.</p>
<p><strong>Induction Hypothesis</strong>: Assume that any graph with less than <span class="math inline">m</span> edges that is connected with all even degrees has an Eulerian circuit.</p>
<p><strong>Induction Step</strong>: Suppose <span class="math inline">G</span> has <span class="math inline">m</span> edges. Start at a vertex <span class="math inline">v</span>, and continue to walk in <span class="math inline">G</span> without repeating edges until we cannot continue. We must have stopped at <span class="math inline">v</span>, since each time we visit another vertex, an odd number of edges are used at that vertex, so we can continue. Let <span class="math inline">W</span> be this closed walk. If <span class="math inline">W</span> contains all edges of <span class="math inline">G</span>, then it is an Eulerian circuit, and we are done. Otherwise, we remove the edges <span class="math inline">W</span> from <span class="math inline">G</span> to obtain the graph <span class="math inline">G^\prime</span>. Since every vertex is incident with an even number of edges in <span class="math inline">W</span>, and it has an even degree in <span class="math inline">G</span>, every vertex has even degree in <span class="math inline">G^\prime</span>. Now, <span class="math inline">G^\prime</span> consists of components with even degrees, and each has less than <span class="math inline">m</span> edges. By induction, each component has of <span class="math inline">G^\prime</span> has an Eulerian circuit. Since <span class="math inline">G</span> is connected, each component of <span class="math inline">G^\prime</span> has a vertex in common with <span class="math inline">W</span>. So we can obtain an Eulerian circuit for <span class="math inline">G</span> by attaching each Eulerian circuit of the components of <span class="math inline">G^\prime</span> at the vertex it has in common with <span class="math inline">W</span>.</p>
</blockquote>
<p><strong>Corollary</strong>: <strong>Edge Disjoint Walks</strong>. If <span class="math inline">G</span> has <span class="math inline">2k</span> odd-degree vertices and is connected, then the edges of <span class="math inline">G</span> can be covered in <span class="math inline">k</span> edge-disjoint walks. We can add edges <span class="math inline">k</span> that pair up odd degree vertices in order to obtain an Eulerian circuit. Removing these <span class="math inline">k</span> added edges will result in a <span class="math inline">k</span> edge disjoint walks.</p>
<h1 id="bridges">Bridges</h1>
<p><strong>Definition</strong>: An edge <span class="math inline">e</span> is a <strong>bridge</strong> of <span class="math inline">G</span> if removing <span class="math inline">e</span> from <span class="math inline">G</span> increases the number of components. Alternate names are <strong>cut-edge</strong>, <strong>isthmus</strong>.</p>
<p><strong>Notation</strong>: We represent removing <span class="math inline">e</span> from <span class="math inline">G</span> as <span class="math inline">G - e</span>.</p>
<p><strong>Theorem</strong>: If <span class="math inline">e=uv</span> is a bridge of a connected graph <span class="math inline">G</span>, then <span class="math inline">G - e</span> has exactly 2 components. Also <span class="math inline">u,v</span> are in different components of <span class="math inline">G - e</span>.</p>
<blockquote>
<p>Suppose, by way of contradiction, that <span class="math inline">G - e</span> has at least 3 components. Let <span class="math inline">H</span> be a component of <span class="math inline">G-e</span> that does not contain <span class="math inline">u</span> nor <span class="math inline">v</span>. So the cut induced by <span class="math inline">V(H)</span> in <span class="math inline">G-e</span> is empty. Since <span class="math inline">u, v</span> are not in <span class="math inline">V(H)</span>, the edge <span class="math inline">uv</span> is not in the cut induced by <span class="math inline">V(H)</span> in <span class="math inline">G</span>. So this cut is still empty in <span class="math inline">G</span>, hence <span class="math inline">G</span> is disconnected. Contradiction.</p>
</blockquote>
<blockquote>
<p>Now suppose <span class="math inline">u,v</span> are in the same component of <span class="math inline">G-e</span>. Let <span class="math inline">J</span> be the other component. So the cut induced by <span class="math inline">V(J)</span> in <span class="math inline">G - e</span> is empty. But <span class="math inline">e=uv</span> is not in the cut induced by <span class="math inline">V(J)</span> in <span class="math inline">G</span>. So this cut is empty in <span class="math inline">G</span>, contradiction.</p>
</blockquote>
<p><strong>Theorem</strong>: <span class="math inline">e</span> is a bridge of <span class="math inline">G</span> if and only if <span class="math inline">e</span> is not in any cycle of <span class="math inline">G</span>.</p>
<blockquote>
<p>(<span class="math inline">\Rightarrow</span>) Suppose <span class="math inline">e</span> is in a cycle <span class="math inline">C</span>. Then in <span class="math inline">G - e</span>, it contains the path <span class="math inline">C - e</span>, which joins the two endpoints of <span class="math inline">e</span>. So they are in the same component. So <span class="math inline">e</span> cannot be a bridge, since the two endpoints of a bridge are in different components of <span class="math inline">G - e</span>.</p>
<p>(<span class="math inline">\Leftarrow</span>) Suppose <span class="math inline">e</span> is not a bridge. Consider component <span class="math inline">H</span> of <span class="math inline">G</span> that contains <span class="math inline">e</span>. Then <span class="math inline">H - e</span> is connected, and has a path <span class="math inline">P</span> joining the two endpoints of <span class="math inline">e</span>. Since <span class="math inline">P</span> does not contain <span class="math inline">e</span>, <span class="math inline">P + e</span> is a cycle in <span class="math inline">G</span> containing <span class="math inline">e</span>.</p>
</blockquote>
<h1 id="trees">Trees</h1>
<p><strong>Definition</strong>: A <strong>tree</strong> is a connected graph with no cycles. A tree is minimally connected.</p>
<p><strong>Definition</strong>: A <strong>forest</strong> is a graph with no cycles.</p>
<p><strong>Lemma</strong>: Every edge in a tree / forest is a bridge.</p>
<blockquote>
<p>No edge is in a cycle, so all edges are bridges.</p>
</blockquote>
<p><strong>Definition</strong>: A <strong>leaf</strong> in a tree / forest is a vertex of degree 1.</p>
<p><strong>Theorem</strong>: A tree with at least 2 vertices has at least 2 leaves.</p>
<blockquote>
<p>Let <span class="math inline">v_0, v_1, ..., v_k</span> be a longest path in a tree <span class="math inline">T</span>. Since <span class="math inline">T</span> has at least 2 vertices, this path has at least one edge. Consider <span class="math inline">v_0</span>. Now <span class="math inline">v_0</span> has a neighbour <span class="math inline">v_1</span>, but <span class="math inline">v_0</span> cannot have a neighbour outside the path, for otherwise we obtain a longer path. Also, <span class="math inline">v_0</span> can not have another neighbour <span class="math inline">v_i</span> in the path, since <span class="math inline">v_0, ..., v_i, v_0</span> would be a cycle. So <span class="math inline">v_0</span> has degree 1, so it is a leaf. Similarly, <span class="math inline">v_k</span> is a leaf. So <span class="math inline">T</span> has at least 2 leaves.</p>
</blockquote>
<p><strong>Theorem</strong>: Every tree with <span class="math inline">n</span> vertices has <span class="math inline">n-1</span> edges.</p>
<blockquote>
<p>We prove by induction on the number of vertices <span class="math inline">n</span>.</p>
<p><strong>Base Case</strong>: When <span class="math inline">n=1</span>, there are <span class="math inline">0 = 1-1</span> edges.</p>
<p><strong>Induction Hypothesis</strong>: Assume that every any tree with <span class="math inline">n - 1</span> vertices has <span class="math inline">n - 2</span> edges, for some <span class="math inline">n \ge 2</span>.</p>
<p><strong>Induction Step</strong>: Let <span class="math inline">T</span> be a tree with <span class="math inline">n</span> vertices. Let <span class="math inline">v</span> be a leaf of <span class="math inline">T</span>, let <span class="math inline">e</span> be its incident edge. <span class="math inline">T - e</span> has 2 components, one of which is just <span class="math inline">v</span>. Let <span class="math inline">T^\prime</span> be obtained from <span class="math inline">T</span> by removing <span class="math inline">e</span> and <span class="math inline">v</span>. <span class="math inline">T^\prime</span> has only one component, and has no cycles. So <span class="math inline">T^\prime</span> is a tree with <span class="math inline">n-1</span> vertices. By induction, <span class="math inline">T^\prime</span> has <span class="math inline">n-2</span> edges. Together with <span class="math inline">e</span>, <span class="math inline">T</span> has <span class="math inline">n-1</span> edges.</p>
</blockquote>
<p><strong>Theorem</strong>: In a forest with <span class="math inline">n</span> vertices and <span class="math inline">k</span> components, there are <span class="math inline">n - k</span> edges.</p>
<blockquote>
<p>In each component, there is one fewer edge than vertices. Over <span class="math inline">k</span> components, there are <span class="math inline">k</span> fewer edges.</p>
</blockquote>
<p><strong>Theorem</strong>: In a tree <span class="math inline">T</span>, there is a unique u,v-path for any <span class="math inline">u,v \in T</span>.</p>
<blockquote>
<p>Suppose there are two u,v-paths, <span class="math inline">P_1</span>, <span class="math inline">P_2</span>. There is an edge <span class="math inline">e</span> in one path, say <span class="math inline">P_1</span>, but not in the other. Consider <span class="math inline">T - e</span>. Suppose <span class="math inline">x</span> is closer to <span class="math inline">u</span> than <span class="math inline">y</span> in <span class="math inline">P_1</span>. Then, the <span class="math inline">xu</span> path in <span class="math inline">P_1</span> followed by the <span class="math inline">uv</span> path <span class="math inline">P_2</span> followed by the <span class="math inline">vy</span> path in <span class="math inline">P_1</span> is an x,y-walk in <span class="math inline">T-e</span>. So <span class="math inline">x,y</span> are in the same component of <span class="math inline">T-e</span>, contradicting the fact that <span class="math inline">e</span> is a bridge. So there is a unique u,v-path in <span class="math inline">T</span>.</p>
</blockquote>
<p><strong>Theorem</strong>: A tree is bipartite.</p>
<blockquote>
<p>Induction on a tree with <span class="math inline">n</span> vertices.</p>
</blockquote>
<h2 id="spanning-trees">Spanning Trees</h2>
<blockquote>
<p><span class="math inline">T</span> is a <strong>spanning tree</strong> of <span class="math inline">G</span> if <span class="math inline">T</span> is a spanning subgraph of <span class="math inline">G</span> that is a tree.</p>
</blockquote>
<p><strong>Theorem</strong>: <span class="math inline">G</span> connected if and only if <span class="math inline">G</span> has a spanning tree.</p>
<blockquote>
<p>(<span class="math inline">\Leftarrow</span>) If <span class="math inline">T</span> is a spanning tree, then there is a u,v-path in <span class="math inline">T</span> for any <span class="math inline">u,v \in V(T)</span>. This path is also in <span class="math inline">G</span>, so <span class="math inline">G</span> is connected.</p>
<p>(<span class="math inline">\Rightarrow</span>) Induction on the number of cycles.</p>
<p><strong>Base Case</strong>: When there are no cycles, <span class="math inline">G</span> is already its own spanning tree.</p>
<p><strong>Induction Hypothesis</strong>: Any connected grpah with fewer cycles than <span class="math inline">G</span> has a spanning tree.</p>
<p><strong>Induction Step</strong>: Since <span class="math inline">G</span> has at least one cycle, <span class="math inline">G</span> has an edge <span class="math inline">e</span> that is not a bridge. Then <span class="math inline">G - e</span> is connected, and has fewer cycles. By induction, <span class="math inline">G - e</span> has a spanning tree <span class="math inline">T</span>. Then <span class="math inline">T</span> is a spanning tree for <span class="math inline">G</span>.</p>
</blockquote>
<p><strong>Corollary</strong>: If <span class="math inline">G</span> is connected with <span class="math inline">n</span> vertices and <span class="math inline">n-1</span> edges, then <span class="math inline">G</span> is a tree.</p>
<blockquote>
<p>Since <span class="math inline">G</span> is connected, it has a spanning tree <span class="math inline">T</span>. Now <span class="math inline">T</span> has <span class="math inline">n-1</span> edges, the same as <span class="math inline">G</span>, so <span class="math inline">G = T</span>.</p>
</blockquote>
<p><strong>Theorem</strong>: Let <span class="math inline">G</span> be a graph with <span class="math inline">n</span> vertices. If any of the 2 conditions hold for <span class="math inline">G</span>, then <span class="math inline">G</span> is a tree.</p>
<ol type="1">
<li><span class="math inline">G</span> is connected.</li>
<li><span class="math inline">G</span> has no cycles.</li>
<li><span class="math inline">G</span> has <span class="math inline">n-1</span> edges.</li>
</ol>
<p><strong>Theorem</strong>: If <span class="math inline">T</span> is a spanning tree of <span class="math inline">G</span> and <span class="math inline">e</span> is an edge of <span class="math inline">G</span> that is not in <span class="math inline">T</span>, then <span class="math inline">T + e</span> contains exactly one cycle <span class="math inline">C</span>. Moreover, if <span class="math inline">e^\prime</span> is any edge in <span class="math inline">C</span>, then <span class="math inline">T + e - e^\prime</span> is also a spanning tree of <span class="math inline">G</span>.</p>
<blockquote>
<p>Let <span class="math inline">e = uv</span>. Since <span class="math inline">T</span> does not have a cycle, any cycle in <span class="math inline">T + e</span> must use <span class="math inline">e</span>. Any such cycle consists of <span class="math inline">e</span> and u,v-path in <span class="math inline">T</span>. But there is a unique u,v-path in <span class="math inline">T</span>, so <span class="math inline">T + e</span> has exactly one cycle <span class="math inline">C</span>. Let <span class="math inline">e^\prime</span> be an edge in <span class="math inline">C</span>. Then <span class="math inline">e^\prime</span> is not a bridge, so <span class="math inline">T + e - e^\prime</span> is connected. Also, removing <span class="math inline">e^\prime</span> destroys the only cycle in <span class="math inline">T + e</span> (or, <span class="math inline">T + e - e^\prime</span> has the same number of edges as <span class="math inline">T</span>). So it is a spanning tree.</p>
</blockquote>
<h2 id="bipartite-characterization">Bipartite Characterization</h2>
<p><strong>Theorem</strong>: <span class="math inline">G</span> is bipartite if and only if <span class="math inline">G</span> does not contain any odd cycle.</p>
<blockquote>
<p>(<span class="math inline">\Rightarrow</span>) Suppose <span class="math inline">G</span> has an odd cycle <span class="math inline">v_1, v_2, ..., v_k, v_1</span>. Suppose <span class="math inline">G</span> has bipartition <span class="math inline">(A, B)</span>, WLOG, assume <span class="math inline">v_1 \in A</span>. Then <span class="math inline">v_2 \in B, v_3 \in A, ...</span>. So <span class="math inline">v_i \in A</span> if and only if <span class="math inline">i</span> is odd. But <span class="math inline">k</span> is odd, and <span class="math inline">v_1v_k</span> is an edge where <span class="math inline">v_k, v_1 \in A</span>. Contradiction.</p>
<p>(<span class="math inline">\Leftarrow</span>) Suppose <span class="math inline">G</span> is not bipartite. Then there is a component <span class="math inline">H</span> of <span class="math inline">G</span> that is not bipartite. Since <span class="math inline">H</span> is connected, it has a spanning tree <span class="math inline">T</span>. Now <span class="math inline">T</span> is bipartite, say with bipartition <span class="math inline">(A, B)</span>. Since <span class="math inline">H</span> is not bipartite, there exists an edge joining two vertices of <span class="math inline">A</span>, or 2 vertices of <span class="math inline">B</span>. WLOG, say <span class="math inline">e=uv</span> where both <span class="math inline">u,v \in A</span>. Let <span class="math inline">P = v_1, v_2, ..., v_k</span> by the unique u,v-path in <span class="math inline">T</span>. Since <span class="math inline">(A, B)</span> is a bipartition of <span class="math inline">T</span>, <span class="math inline">v_1, v_3, ... \in A</span>, <span class="math inline">v_2, v_4, ..., \in B</span>. Since <span class="math inline">v_k \in A</span>, <span class="math inline">k</span> is odd, so <span class="math inline">P</span> has even length. So <span class="math inline">P + e</span> is a cycle of odd length in <span class="math inline">G</span>.</p>
</blockquote>
<h2 id="minimum-spanning-trees">Minimum Spanning Trees</h2>
<p><strong>Given</strong> a connected graph <span class="math inline">G</span> with weights / costs on edges <span class="math inline">w: E(G) \to \mathbb{R}</span>.</p>
<p><strong>Goal</strong>: Find a spanning tree in <span class="math inline">G</span> whose total edge weight is minimized.</p>
<h3 id="prims-algorithm">Prim’s Algorithm</h3>
<ol type="1">
<li>Let <span class="math inline">v</span> be any vertex in <span class="math inline">G</span>. Let <span class="math inline">T</span> be the tree consists of only <span class="math inline">v</span>.</li>
<li>While <span class="math inline">T</span> is not a spanning tree …
<ul>
<li>Look at edges in the cut induced by <span class="math inline">V(T)</span>.</li>
<li>Let <span class="math inline">e=uv</span> be an edge with the smallest weight in the cut, say <span class="math inline">u\in V(T), v \notin V(T)</span>.</li>
<li>Add <span class="math inline">v</span> to <span class="math inline">V(T)</span>, add <span class="math inline">e</span> to <span class="math inline">E(T)</span>.</li>
</ul></li>
</ol>
<p><strong>Theorem</strong>: Prim’s algorithm produces a MST.</p>
<blockquote>
<p>Let <span class="math inline">T_1, T_2, ..., T_n</span> be the trees produced by the algorithm at each step. Suppose the edges we select in order are <span class="math inline">e_1, e_2, .., e_{n-1}</span>, so we get <span class="math inline">T_{i+1}</span> by adding <span class="math inline">e_i</span> to <span class="math inline">T_i</span>. We will prove by induction on <span class="math inline">k</span> that there exists a MST containing <span class="math inline">T_k</span> as a subgraph.</p>
<p><strong>Base Case</strong>: <span class="math inline">T_1</span> is a single vertex, which is a subgraph of any MST.</p>
<p><strong>Induction Hypothesis</strong>: Assume that <span class="math inline">T_k</span> is a subgraph of some MST <span class="math inline">T^*</span>.</p>
<p><strong>Induction Step</strong>: If <span class="math inline">T^*</span> contains <span class="math inline">e_k</span>, then <span class="math inline">T^*</span> is a MST containing <span class="math inline">T_{k+1}</span>, and we are done. Assume <span class="math inline">e_k</span> is not in <span class="math inline">T^*</span>. Then, <span class="math inline">T^* + e_k</span> has exactly one cycle <span class="math inline">C</span>. Then there is an edge <span class="math inline">e^\prime</span> in <span class="math inline">C</span> that is not <span class="math inline">e_k</span>, but is in the cut induced by <span class="math inline">V(T_k)</span>. In Prim’s algorithm, <span class="math inline">e_k</span> is chosen to be an edge of minimum weight in the cut induced by <span class="math inline">V(T_k)</span>. So <span class="math inline">w(e^\prime) \ge w(e_k)</span>.</p>
<p>Suppose <span class="math inline">w(e^\prime) > w(e_k)</span>. Let <span class="math inline">T^\prime = T^* + e_k - e^\prime</span>. <span class="math inline">T^\prime</span> is a spanning tree with a lower weight than <span class="math inline">T^*</span>, but <span class="math inline">T^*</span> is a MST. Contradiction.</p>
<p>Suppose <span class="math inline">w(e^\prime) = w(e_k)</span>. Then <span class="math inline">T^\prime</span> is a spanning tree with the same weight of <span class="math inline">T^*</span>. So <span class="math inline">T^\prime</span> is a MST containing <span class="math inline">T_{k+1}</span>.</p>
<p>So <span class="math inline">T_n</span> is a spanning tree that contains a MST. But they have the same number of edges, so they are the same.</p>
</blockquote>
<h1 id="travelling-salesman-problem-tsp">Travelling Salesman Problem (TSP)</h1>
<p>Given <span class="math inline">K_n</span> with edge weights <span class="math inline">w</span>, we want to find a cycle containing all vertices (<strong>Hamilton cycle</strong>) that has minimum weight.</p>
<h2 id="heuristic-for-euclidean-tsp">Heuristic for Euclidean TSP</h2>
<ol type="1">
<li>Find MST <span class="math inline">T</span>.</li>
<li>Double edges.</li>
<li>Find Eulerian circuit.</li>
<li>Go through Eulerian circuit, skipping vertices.</li>
</ol>
<p><strong>Theorem</strong>: If <span class="math inline">C</span> is the cycle produced by the heuristic, and <span class="math inline">C^*</span> a best cycle, then <span class="math inline">w(C) \le 2w(C^*)</span>.</p>
<blockquote>
<p><span class="math inline">C^*</span> minus an edge is a spanning tree, so the cost of <span class="math inline">w(C^*) \ge w(T)</span>. With <span class="math inline">C</span>, we take “shortcuts” using the triangle inequality, so <span class="math inline">W(C) \le 2W(T)</span>. So <span class="math inline">W(C) \le 2w(C^*)</span>.</p>
</blockquote>
<h1 id="planar-graphs">Planar Graphs</h1>
<p><strong>Definition</strong>: A <strong>planar embedding</strong> of <span class="math inline">G</span> is a drawing of <span class="math inline">G</span> on the plane such that the vertices are at different points, and the edges are lines that do not cross each other. A graph that has a planar embedding is a <strong>planar graph</strong>.</p>
<p><strong>Definition</strong>: A <strong>face</strong> of a planar embedding is a connected region on the plane that includes no point of any edges.</p>
<p><strong>Definition</strong>: For a connected planar embedding, the <strong>boundary walk</strong> for a face is a closed walk on the edges that form the boundary of the region, going around once. The <strong>degree</strong> of a face is the length of its boundary walk, <span class="math inline">deg(f)</span>.</p>
<p><strong>Handshaking Lemma for Faces</strong>: Let <span class="math inline">G</span> be a planar graph with an embedding with <span class="math inline">F</span> as the set of all faces. Then <span class="math inline">\sum_{f \in F}deg(f) = 2|E(G)|</span>.</p>
<blockquote>
<p>Each edge contributes 2 to the sum of the face degrees, one for each side of the edge.</p>
</blockquote>
<p><strong>Observation</strong>: <span class="math inline">e</span> is a bridge if and only if the two sides of <span class="math inline">e</span> are in the same face.</p>
<p><strong>Jordon Curve Theorem</strong>: Every simple closed curve on the plane separates it into 2 parts, one inside, one outside.</p>
<h2 id="eulers-formula">Euler’s Formula</h2>
<p>A planar graph could have several non-equivalent embeddings (different faces). The number of faces is always the same. This is a result of Euler’s formula.</p>
<p><strong>Euler’s Formula</strong>: For a planar embedding of a connected graph <span class="math inline">G</span>, with <span class="math inline">n</span> vertices, <span class="math inline">m</span> edges, and <span class="math inline">s</span> faces, <span class="math inline">n - m + s = 2</span>.</p>
<p>A planar graph <span class="math inline">G</span> with <span class="math inline">n</span> vertices and <span class="math inline">m</span> edges can have at most <span class="math inline">3n - 6</span> edges.</p>
<blockquote>
<p>We know that if a face has degree greater than 3, we can always add an edge between them, so in an edge-maximal planar graph, all faces must be triangles. Let us count the number of edges in the graph. We have that <span class="math inline">2m = 3F</span>. Using <span class="math inline">F = 2 - n + m</span>, we can obtain an upper bound on the number of edges. <span class="math display">\begin{aligned}2m &\ge 3(2 - n + m) \\ 2m &\ge 6 - 3n + 3m \\ 3n - 6 &\ge m\end{aligned}</span></p>
</blockquote>
<blockquote>
<p>For bipartite graphs, the smallest face now must have an even degree, so 4. <span class="math display">\begin{aligned}2m &\ge 4(2 - n + m) \\ 2m &\ge 8 - 4n + 4m \\ 2n - 4 &\ge m\end{aligned}</span></p>
</blockquote>
<h1 id="platonic-solids">Platonic Solids</h1>
<p>Given a planar embedding, we can draw it on a sphere, then cut across each face to obtain a polyhedron.</p>
<p><strong>Definition</strong>: A connected planar graph is <strong>platonic</strong> if it has an embedding where every vertex has the same degree (<span class="math inline">\ge 3</span>) and every face has the same degree (<span class="math inline">\ge 3</span>).</p>
<p>Suppose a platonic graph has <span class="math inline">n</span> vertices, <span class="math inline">m</span> edges, <span class="math inline">s</span> faces, vertex degree <span class="math inline">d_v \ge 3</span>, and face degree <span class="math inline">d_f \ge 3</span>.</p>
<ol type="1">
<li>By handshaking lemma, <span class="math inline">2m = d_v n \Rightarrow n = \frac{2m}{d_v}</span>.</li>
<li>By handshaking lemma for faces, <span class="math inline">2m = d_f s \Rightarrow s = \frac{2m}{d_f}</span>.</li>
<li>By Euler’s formula, <span class="math inline">n - m + s = 2</span>.</li>
</ol>
<p>By substituting <span class="math inline">1,2\to 3</span>.</p>
<p><span class="math display">\begin{aligned}
\frac{2m}{d_v} - m + \frac{2m}{d_f} &= 2 \\
2md_f - md_vd_f + 2md_v &= 2d_vd_f \\
2md_f - md_vd_f + 2md_v &> 0 \\
2d_f - d_vd_f + 2d_v -4 + 4 &> 0 \\
-(d_v -2 )(d_f - 2) + 4 &> 0 \\
4 &> (d_v - 2)(d_f - 2)
\end{aligned}</span></p>
<p>Combinations of <span class="math inline">(d_v, d_f)</span> that satisfy the inequality:</p>
<table>
<thead>
<tr class="header">
<th><span class="math inline">d_v</span></th>
<th><span class="math inline">d_f</span></th>
</tr>
</thead>
<tbody>
<tr class="odd">
<td><span class="math inline">3</span></td>
<td><span class="math inline">3,4,5</span></td>
</tr>
<tr class="even">
<td><span class="math inline">4</span></td>
<td><span class="math inline">3</span></td>
</tr>
<tr class="odd">
<td><span class="math inline">5</span></td>
<td><span class="math inline">3</span></td>
</tr>
</tbody>
</table>
<h1 id="kuratowskis-theorem">Kuratowski’s Theorem</h1>
<p><strong>Definition</strong>: An <strong>edge subdivision</strong> of a graph is obtained by replacing each edge with a new path of length at least 1. Drawing an edge is equivalent to drawing a path.</p>
<p><strong>Lemma</strong>: <span class="math inline">G</span> is planar if and only if any edge subdivision of <span class="math inline">G</span> is planar.</p>
<p>So any edge subdivisions of <span class="math inline">K_5</span> and <span class="math inline">K_{3,3}</span> are non-planar.</p>
<p><strong>Kuratowski’s Theorem</strong>: <span class="math inline">G</span> is planar if and only if <span class="math inline">G</span> does not contain any edge subdivision of <span class="math inline">K_5</span> or <span class="math inline">K_{3,3}</span>.</p>
<p><strong>Notes</strong></p>
<ol type="1">
<li>In your edge subdivision vertices that are not the main 5/6 vertices of <span class="math inline">K_5</span>/<span class="math inline">K_{3,3}</span> can be used at most once.</li>
<li>Usually you can find a <span class="math inline">K_{3,3}</span> subdivision.</li>
</ol>
<h1 id="colouring">Colouring</h1>
<p><strong>Definition</strong>: A <strong>k-colouring</strong> in <span class="math inline">G</span> is an assignment of a colour to each vertex of <span class="math inline">G</span> using at most <span class="math inline">k</span> colours, such that adjacent vertices receive different colours. A graph that has a k-colouring is called <strong>k-colourable</strong>.</p>
<p><strong>General Question</strong>: What is the <strong>minimum</strong> number of colours we need to colour a graph?</p>
<p><strong>Theorem</strong>: <span class="math inline">K_n</span> is n-colourable, but not (n-1)-colourable.</p>
<p><strong>Theorem</strong>: A graph is 2-colourable if and only if it is bipartite.</p>
<h2 id="colouring-planar-graphs">Colouring Planar Graphs</h2>
<p><strong>Lemma</strong>: Every planar graph has a vertex of degree at most 5.</p>
<blockquote>
<p>Suppose, by way of contradiction, that every vertex has degree at least 6. By Handshaking Lemma, the number of edges is at least <span class="math inline">3n</span>. But <span class="math inline">G</span> is planar, and has at most <span class="math inline">3n-6</span>, contradiction.</p>
</blockquote>
<p><strong>Theorem</strong>: Every planar graph is 6-colourable.</p>
<blockquote>
<p>By induction on the number of vertices <span class="math inline">n</span>.</p>
<p><strong>Base Case</strong>: When <span class="math inline">n = 1</span>, <span class="math inline">G</span> is a single vertex, which is 6-colourable.</p>
<p><strong>Induction Hypothesis</strong>: Every planar graph with <span class="math inline">n-1</span> vertices is 6 colourable.</p>
<p><strong>Induction Step</strong>: Let <span class="math inline">G</span> be a planar graph on <span class="math inline">n</span> vertices. Let <span class="math inline">v</span> be a vertex of <span class="math inline">G</span> with degree at most <span class="math inline">5</span>. Let <span class="math inline">G^\prime</span> be obtained from <span class="math inline">G</span> by removing <span class="math inline">v</span> and its incident edges. So <span class="math inline">G^\prime</span> is planar with <span class="math inline">n-1</span> vertices. By induction hypothesis, <span class="math inline">G^\prime</span> is 6-colourable. We keep the same colouring for <span class="math inline">G</span>. The neighbours of <span class="math inline">v</span> use up to 5 different colours. Since we have 6 colours, there is one unused by the neighbours of <span class="math inline">v</span>. We assign that colour to <span class="math inline">v</span> to obtain a 6-colouring of <span class="math inline">G</span>.</p>
</blockquote>
<p><strong>Contraction</strong>: Collapse vertices <span class="math inline">uv</span> along an edge <span class="math inline">e</span>.</p>
<ul>
<li>Contractions may result in multiple edges. However, this does not affect colouring, so we can remove them.</li>
</ul>
<p><strong>Observation</strong>: If <span class="math inline">G</span> is planar, then <span class="math inline">G \setminus e</span> is planar.</p>
<p><strong>Theorem</strong>: Every planar graph is 5-colourable.</p>
<blockquote>
<p>Strong induction on the number of vertices <span class="math inline">n</span>.</p>
<p><strong>Base Case</strong>: Any planar graph with at most 5 vertices is 5-colourable.</p>
<p><strong>Induction Hypothesis</strong>: Any planar graph with at most <span class="math inline">n-1</span> vertices is 5-colourable.</p>
<p><strong>Induction Step</strong>: Let <span class="math inline">G</span> be planar with <span class="math inline">n</span> vertices. Let <span class="math inline">v</span> be a vertex in <span class="math inline">G</span> with degree at most 5. If <span class="math inline">deg(v) \le 4</span>, then we can 5-colour the graph with <span class="math inline">v</span> and its incident edges removed, and assign <span class="math inline">v</span> an unused colour in its neighbours. If <span class="math inline">deg(v) = 5</span>, then there exists two neighbours of <span class="math inline">v</span>, say <span class="math inline">x,y</span> that are not adjacent, for otherwise the neighbours of <span class="math inline">v</span> form <span class="math inline">K_5</span>, which is not planar. Let <span class="math inline">H</span> be the graph obtained from <span class="math inline">G</span> by contacting <span class="math inline">vx</span> and <span class="math inline">vy</span>. Let <span class="math inline">z</span> be the contracted vertex. Since contraction preserves planarity, <span class="math inline">H</span> is planar, and <span class="math inline">H</span> has <span class="math inline">n-2</span> vertices. So <span class="math inline">H</span> is 5-colourable by induction. Keep this colouring for <span class="math inline">G</span>, except <span class="math inline">v,x,y</span>. We colour <span class="math inline">x,y</span> with the colour of <span class="math inline">z</span>. This is possible since <span class="math inline">x,y</span> are not adjacent, and neighbours of <span class="math inline">x,y</span> in <span class="math inline">G</span> are neighbours of <span class="math inline">z</span> in <span class="math inline">H</span>. Now neighbours of <span class="math inline">v</span> use at most 4 colours. Since we have 5 colours, there is one unused colour that we can assign to <span class="math inline">v</span>. This gives a 5-colouring for <span class="math inline">G</span>.</p>
</blockquote>
<p><strong>Theorem</strong>: Every planar graph is 4-colourable.</p>
<h1 id="dual-graphs">Dual Graphs</h1>
<p><strong>Definition</strong>: Let <span class="math inline">G</span> be a planar graph with an embedding. The <em>dual</em> <span class="math inline">G^*</span> of <span class="math inline">G</span> has one vertex <span class="math inline">v_f</span> corresponding to each face <span class="math inline">f</span> of the embedding, and for each edge in <span class="math inline">G</span> whose two sides are the faces <span class="math inline">f_1</span> and <span class="math inline">f_2</span>, <span class="math inline">G^*</span> has a corresponding edges.</p>
<ul>
<li><span class="math inline">G^*</span> is planar.</li>
<li><span class="math inline">G^{**} = G</span>.</li>
<li>The number of faces in <span class="math inline">G</span> is the number of vertices in <span class="math inline">G^*</span>.</li>
<li>The number of vertices in <span class="math inline">G</span> is the number of faces in <span class="math inline">G^*</span>.</li>
<li>The number of edges is preserved.</li>
<li>Face degrees in <span class="math inline">G</span> become vertex degrees of <span class="math inline">G^*</span> and vertex degrees become face degrees.</li>
<li>The dual of a platonic graph is platonic.</li>
</ul>
<h1 id="matching">Matching</h1>
<p><strong>Definition</strong>: A <strong>matching</strong> is a set of edges where no two edges share a common vertex.</p>
<p><strong>General Question</strong>: What is the maximum size of a matching in a graph.</p>
<p><strong>Definition</strong>: A vertex incident with an edge in a matching is <strong>saturated</strong>. Otherwise it is <strong>unsaturated</strong>.</p>
<p>A matching that saturates every vertex is a <strong>perfect matching</strong>.</p>
<h1 id="cover">Cover</h1>
<p><strong>Definition</strong>: A <strong>cover</strong> of <span class="math inline">G</span> is a set of vertices such that each edge of <span class="math inline">G</span> is incident with at least one vertex in the set.</p>
<p><strong>General Question</strong>: What is the minimum size of a cover in a graph?</p>
<p>Relation between a matching <span class="math inline">M</span> and a cover <span class="math inline">C</span> in <span class="math inline">G</span>.</p>
<blockquote>
<p><span class="math inline">C</span> must use <strong>at least</strong> one vertex from each matching edge. So <span class="math inline">|C| \ge |M|</span>.</p>
</blockquote>
<p><strong>Theorem</strong>: If <span class="math inline">M</span> is any matching and <span class="math inline">C</span> is any cover of <span class="math inline">G</span>, then <span class="math inline">|C| \ge |M|</span>.</p>
<blockquote>
<p>For each edge <span class="math inline">uv</span> in <span class="math inline">M</span>, at least one of <span class="math inline">u</span> or <span class="math inline">v</span> is in <span class="math inline">C</span> since <span class="math inline">C</span> covers the edge. Also, different edges in <span class="math inline">M</span> use different vertices, so the vertices in <span class="math inline">C</span> from different matching edges are distinct. So <span class="math inline">|C| \ge |M|</span>.</p>
</blockquote>
<p><strong>Corollary</strong>: If <span class="math inline">M</span> is a matching and <span class="math inline">C</span> is a cover of <span class="math inline">G</span> where <span class="math inline">M = C</span>, then <span class="math inline">M</span> is a maximum matching and <span class="math inline">C</span> is a minimum cover.</p>
<blockquote>
<p>Let <span class="math inline">M^\prime</span> be any matching, then <span class="math inline">|M^\prime| \le |C|</span>. By assumption, <span class="math inline">|C| = |M|</span>, so <span class="math inline">|M^\prime| \le |M|</span>. Since <span class="math inline">M^\prime</span> is arbitrary, <span class="math inline">M</span> must be a maximum matching.</p>
</blockquote>
<p>One way to prove that a matching is maximum is by providing a cover of the same size. There are examples where the maximum matching is strictly less than the minimum cover such as <span class="math inline">K_3</span>.</p>
<h2 id="augmenting-paths">Augmenting Paths</h2>
<p><strong>Definition</strong>: An <strong>alternating</strong> path with respect to a matching <span class="math inline">M</span> is a path where consecutive edges alternate between being in <span class="math inline">M</span> and not in <span class="math inline">M</span>.</p>
<p><strong>Definition</strong>: An <strong>augmenting path</strong> is an alternating path that starts and ends with different unsaturated vertices.</p>
<p>If we have an augmenting path, then we can enlarge our matching by switching edges in <span class="math inline">M</span> and not in <span class="math inline">M</span>.</p>
<p><strong>Theorem</strong>: If there exists an augmenting path with respect to a matching <span class="math inline">M</span>, then <span class="math inline">M</span> is not a maximum matching.</p>
<p>The converse is also true.</p>
<h2 id="bipartite-matching-algorithm">Bipartite Matching Algorithm</h2>
<p>Given bipartite graph, we will repeatedly find augmenting paths to enlarge a matching. When we can’t find one, we would have produced a matching and a cover of the same size.</p>
<p>What does an augmenting path look like in a bipartite graph?</p>
<p>Suppose wlog it starts in <span class="math inline">A</span>. Then it must end in <span class="math inline">B</span>.</p>
<h2 id="kőnigs-theorem">Kőnig’s Theorem</h2>
<p>In a bipartite graph, the size of a maximum matching is equal to the size of a minimum cover.</p>
<blockquote>
<p>Let <span class="math inline">G</span> be a bipartite graph with bipartition <span class="math inline">(A, B)</span>. Let <span class="math inline">M</span> be a maximum matching produced by the algorithm. Let <span class="math inline">X_0, X, Y</span> be the three sets produced at the end of the algorithm.</p>
<p>First we see that there is no edge joining <span class="math inline">X</span> with <span class="math inline">B \setminus Y</span>. Otherwise, we could extend an alternating path to reach the vertex in <span class="math inline">B \setminus Y</span>, which is not possibly by the definition of <span class="math inline">Y</span>. Then all edges have an endpoint in <span class="math inline">Y</span> or <span class="math inline">A \setminus X</span>. So <span class="math inline">Y \cup (A \setminus X)</span> is a cover.</p>
<p>Now every vertex in <span class="math inline">Y</span> is saturated, for otherwise we would have found an augmenting path and our matching would not be maximum. Also, vertices in <span class="math inline">A \setminus X</span> are saturated, since all unsaturated vertices in <span class="math inline">A</span> are in <span class="math inline">X_0 \subseteq X</span>. No matching edges joins <span class="math inline">Y</span> with <span class="math inline">A \setminus X</span>, for otherwise we could find an alternating path which reaches a vertex in <span class="math inline">A \setminus X</span> which is not possible. So the matching edges that saturate <span class="math inline">Y</span> and <span class="math inline">A \setminus X</span> are distinct. So <span class="math inline">|Y \cup (A \setminus X)| = |M|</span>.</p>
</blockquote>
<p><strong>Corollary</strong>: A bipartite graph <span class="math inline">G</span> with <span class="math inline">m</span> edges and maximum degree <span class="math inline">d</span> has a matching of size at least <span class="math inline">\frac{m}{d}</span>.</p>
<blockquote>
<p>Let <span class="math inline">C</span> be any cover of <span class="math inline">G</span>. Each vertex in <span class="math inline">C</span> has degree at most <span class="math inline">d</span>, so it covers at most <span class="math inline">d</span> edges. Since there are <span class="math inline">m</span> edges to cover, we need at least <span class="math inline">\frac{m}{d}</span> vertices to cover all of them. So <span class="math inline">|C| \ge \frac{m}{d}</span>. So a minimum cover has size at least <span class="math inline">\frac{m}{d}</span>. Since <span class="math inline">G</span> is bipartite, by Kőnig’s Theorem, a maximum matching also has size at least <span class="math inline">\frac{m}{d}</span>.</p>
</blockquote>
<h1 id="halls-theorem">Hall’s Theorem</h1>
<p>Let <span class="math inline">G</span> be a bipartite graph with bipartition <span class="math inline">(A, B)</span>. What are the necessary and sufficient conditions for the existence of a matching that saturates <span class="math inline">A</span>?</p>
<p><strong>Definition</strong>: Let <span class="math inline">D \subseteq V(G)</span>. Then the <strong>neighbour set</strong> of <span class="math inline">N(D)</span> of <span class="math inline">D</span> is is the set of all vertices in <span class="math inline">G</span> adjacent to at least one vertex in <span class="math inline">D</span>.</p>
<p><strong>Hall’s Condition</strong>: For any <span class="math inline">S \subseteq A</span>, <span class="math inline">|S| \le |N(S)|</span>.</p>
<p><strong>Hall’s Theorem</strong>: Let <span class="math inline">G</span> be a bipartite graph with bipartition <span class="math inline">(A, B)</span>. Then there is a matching that saturates every vertex in <span class="math inline">A</span> if and only if for all <span class="math inline">D \subseteq A</span>, <span class="math inline">|N(D)| \ge |D|</span>.</p>
<blockquote>
<p>(<span class="math inline">\Rightarrow</span>) Suppose <span class="math inline">M</span> is a matching that saturates <span class="math inline">A</span>. For any <span class="math inline">D \subseteq A</span>, the matching edges in <span class="math inline">M</span> with one endpoint in <span class="math inline">D</span> have the other endpoint in distinct vertices of <span class="math inline">N(D)</span>. So <span class="math inline">|N(D)| \ge |D|</span>.</p>
<p>(<span class="math inline">\Leftarrow</span>) Suppose <span class="math inline">G</span> does not have a matching that saturates <span class="math inline">A</span>. Let <span class="math inline">M</span> be a maximum matching. Since <span class="math inline">M</span> does not saturate <span class="math inline">A</span>, <span class="math inline">|M| < |A|</span>. By Kőnig Theorem, there exists a cover <span class="math inline">C</span> where <span class="math inline">|C| = |M|</span>. Since <span class="math inline">C</span> is a cover, there is no edge between <span class="math inline">A \setminus C</span> and <span class="math inline">B \setminus C</span>. So the neighbour set of <span class="math inline">N(A \setminus C) \subseteq C \cap B</span>. <span class="math display">\begin{aligned}|N(A \setminus C)| &\le |C \cap B| \\ &= |C| - |C \cap A| \\ &= |M| - |C \cap A| \\ &< |A| - |C \cap A| \\ &= |A \setminus C|\end{aligned}</span> So <span class="math inline">A \setminus C</span> violates Hall’s Condition.</p>
</blockquote>
<p><strong>Corollary</strong>: If <span class="math inline">G</span> is a k-regular bipartite graph with <span class="math inline">k \ge 1</span>, then <span class="math inline">G</span> has a perfect matching.</p>
<blockquote>
<p>Suppose <span class="math inline">G</span> has bipartition <span class="math inline">(A, B)</span>. So <span class="math inline">|A| = |B|</span>. Let <span class="math inline">D \subseteq A</span>. Since each vertex has degree <span class="math inline">k</span>, there are <span class="math inline">k|D|</span> edges incident with a vertex in <span class="math inline">D</span>. Each such edge ends in <span class="math inline">N(D)</span>. So <span class="math inline">\sum_{v \in N(D)} deg(v) \ge k|D|</span>. So <span class="math inline">k|N(D)| \ge k|D|</span>. Since <span class="math inline">k \ge 1</span>, <span class="math inline">|N(D)| \ge |D|</span>. By Hall’s Theorem, there is a matching that saturates <span class="math inline">A</span>. Since <span class="math inline">|A| = |B|</span>, it must be a perfect matching.</p>
</blockquote>
<p><strong>Corollary</strong>: The edges of a k-regular bipartite graph can be partitioned into <span class="math inline">k</span> perfect matchings.</p>
<blockquote>
<p>Induction on <span class="math inline">k</span>. Removing a perfect matching leaves a (k-1)-regular bipartite graph.</p>
</blockquote>
</body>
</html>