PGg1PjxpIGNsYXNzPSJpY29uLWxpbmsiPjwvaT4mbmJzcDsmbmJzcDsKICAgIEZpbmFsIEV4YW0KPC9oNT4KCjxkaXYgZGF0YS1jbGFzcz0icXVpY2stbGlua3MiPgogICAgPGEgY2xhc3M9ImJ0biIgaHJlZj0iaHR0cHM6Ly9va2xhaG9tYS56b29tLnVzL2ovOTgyODQ3MzMyMzk/cHdkPVYzZFhhVEZpWkhWbVZUZ3pLM1pUWld0RWRtVnBkejA5IgogICAgICAgID5ab29tIE1lZXRpbmcgKERlYyAxNiwgNzo1MGFtKTwvYT4KICAgIDxhIGNsYXNzPSJidG4iIGhyZWY9Imh0dHBzOi8vY2FudmFzLm91LmVkdS9jb3Vyc2VzLzE4Mzg0OC9hc3NpZ25tZW50cy8xMzM1NzkxIgogICAgICAgID5GaW5hbCBFeGFtIChDYW52YXMgQXNzaWdubWVudCk8L2E+CjwvZGl2PgoKPGg1PjxpIGNsYXNzPSJpY29uLWxpbmsiPjwvaT4mbmJzcDsmbmJzcDsKICAgIFF1aWNrIExpbmtzCjwvaDU+Cgo8ZGl2IGRhdGEtY2xhc3M9InF1aWNrLWxpbmtzIj4KICAgIDxhIGNsYXNzPSJidG4iIGhyZWY9Imh0dHBzOi8vY2FudmFzLm91LmVkdS9jb3Vyc2VzLzE4Mzg0OC9wYWdlcy9ncmFwaC10aGVvcnkiCiAgICAgICAgPlN5bGxhYnVzPC9hPgogICAgPGEgY2xhc3M9ImJ0biIgaHJlZj0iaHR0cHM6Ly9jYW52YXMub3UuZWR1L2NvdXJzZXMvMTgzODQ4L3BhZ2VzL3RpbWVsaW5lIgogICAgICAgID5UaW1lbGluZTwvYT4KICAgIDxhIGNsYXNzPSJidG4iIGhyZWY9Imh0dHBzOi8vY2FudmFzLm91LmVkdS9jb3Vyc2VzLzE4Mzg0OC9wYWdlcy90ZXh0Ym9vayIKICAgICAgICA+VGV4dGJvb2s8L2E+CiAgICA8YSBjbGFzcz0iYnRuIiBocmVmPSJodHRwczovL2NhbnZhcy5vdS5lZHUvY291cnNlcy8xODM4NDgvYXNzaWdubWVudHMiCiAgICAgICAgPkhvbWV3b3JrPC9hPgogICAgPGEgY2xhc3M9ImJ0biIgaHJlZj0iaHR0cHM6Ly9jYW52YXMub3UuZWR1L2NvdXJzZXMvMTgzODQ4L2dyYWRlcyIKICAgICAgICA+R3JhZGVzPC9hPgo8L2Rpdj4KCjxoNT48aSBjbGFzcz0iaWNvbi1tb2R1bGUiPjwvaT4mbmJzcDsmbmJzcDsKICAgIEdyYXBoIFRoZW9yeQo8L2g1PgoKPHA+CkNhbiB5b3UgZmluZCBhIHdhbGsgdGhhdCBjcm9zc2VzIGVhY2ggYnJpZGdlIG9uY2UgYW5kIGV4YWN0bHkgb25jZT8KCjxwIGRhdGEtY2xhc3M9ImNlbnRlciI+CjxpbWcgCiAgICBzcmM9Ii9jb3Vyc2VzLzE4Mzg0OC9maWxlcy8yODQ1Mzg5Mi9wcmV2aWV3IgogICAgYWx0PSJCcmlkZ2VzIgogICAgd2lkdGg9IjYwMCIKICAgIGhlaWdodD0iMjIxIgogICAgZGF0YS1kZWNvcmF0aXZlPSJ0cnVlIgo+Cgo8cD4KQ29sb3IgYSBtYXAgd2l0aCBuIGNvbG9ycyBzbyB0aGF0IG5vIHR3byBhZGphY2VudCBjb3VudHJpZXMgYXJlIGNvbG9yZWQgdGhlCnNhbWUuIFdoYXQgaXMgdGhlIGxlYXN0IG51bWJlciBuIHRoYXQgd29ya3MgZm9yIGFueSBtYXA/IEZvciB0aGUgbWFwIG9mIFVTCkNvdW50aWVzLCB5b3Ugb25seSBuZWVkIDQgY29sb3JzOgoKPHAgZGF0YS1jbGFzcz0iY2VudGVyIj4KPGltZyAKICAgIHNyYz0iL2NvdXJzZXMvMTgzODQ4L2ZpbGVzLzI4NDU1ODI2L3ByZXZpZXciCiAgICBhbHQ9IkJyaWRnZXMiCiAgICB3aWR0aD0iNjAwIgogICAgaGVpZ2h0PSIyMjEiCiAgICBkYXRhLWRlY29yYXRpdmU9InRydWUiCj4KCjxwPgpJZiB0aGUgY29zdCB0byB0cmF2ZWwgYmV0d2VlbiBhbnkgMiBuYXRpb25hbCBwYXJrcyBpbiB0aGUgVVNBIGlzIGtub3duIHdoYXQgaXMKdGhlIGNoZWFwZXN0IHdheSB0byB2aXNpdCBhbGwgb2YgdGhlIHBhcmtzIGV4YWN0bHkgb25jZT8KCjxwPgpPbmUgY29tbW9uIHRoZW1lIHNoYXJlZCBieSBhbGwgb2YgdGhlc2UgcHJvYmxlbXMgaXMgdGhhdCB0aGV5IGNhbiBiZSB0cmFuc2xhdGVkCmludG8gcHJvYmxlbXMgaW52b2x2aW5nIGEgbWF0aGVtYXRpY2FsIGNvbmNlcHQga25vd24gYXMgYSA8Yj5ncmFwaDwvYj4uCgo8aDU+PGkgY2xhc3M9Imljb24tcXVpeiI+PC9pPiZuYnNwOyZuYnNwOwogICAgQ291cnNlIERlc2NyaXB0aW9uCjwvaDU+Cgo8cD4KVGhpcyBpcyBhIGludHJvZHVjdG9yeSBjb3Vyc2Ugb24gcHJvcGVydGllcyBhbmQgYXBwbGljYXRpb25zIG9mIGdyYXBocy4KV2Ugd2lsbCBzdHVkeSBncmFwaC10aGVvcmV0aWMgY29uY2VwdHMgc3VjaCBhcyBwYXRocywgRXVsZXJpYW4gY2lyY3VpdHMsIHRyZWVzLApkaXN0YW5jZSwgbWF0Y2hpbmdzLCBjb25uZWN0aXZpdHksIG5ldHdvcmsgZmxvd3MsIGNvbG9yaW5ncywgcGxhbmFyaXR5LCBhbmQKc3Bhbm5pbmcgY3ljbGVzLiBBIHByaW1hcnkgZ29hbCBpcyB0byBpbXByb3ZlIHN0dWRlbnRzJyBjbGFyaXR5IG9mIHRob3VnaHQgYW5kCmxhbmd1YWdlIHdoZW4gd3JpdGluZyBwcm9vZnMgaW4gZGlzY3JldGUgbWF0aGVtYXRpY3MuCgo8cD4KRmFtb3VzIGFwcGxpY2F0aW9ucyBpbmNsdWRlOgoKPHVsPgogICAgPGxpPnRoZSBNaW5pbXVtIENvbm5lY3RvciBQcm9ibGVtIChidWlsZGluZyByb2FkcyBhdCBtaW5pbXVtIGNvc3QpLAogICAgPGxpPnRoZSBNYXJyaWFnZSBQcm9ibGVtIChtYXRjaGluZyBtZW4gYW5kIHdvbWVuIGludG8gY29tcGF0aWJsZSBwYWlycyksCiAgICA8bGk+dGhlIEFzc2lnbm1lbnQgUHJvYmxlbSAoZmlsbGluZyBuIGpvYnMgaW4gdGhlIGJlc3Qgd2F5KSwKICAgIDxsaT50aGUgTmV0d29yayBGbG93IFByb2JsZW0gKG1heGltaXppbmcgZmxvdyBpbiBhIG5ldHdvcmsgb2YgcGlwZXMpLAogICAgPGxpPnRoZSBDb21taXR0ZWUgU2NoZWR1bGluZyBQcm9ibGVtICh1c2luZyB0aGUgZmV3ZXN0IHRpbWUgc2xvdHMpLAogICAgPGxpPnRoZSBGb3VyIENvbG9yIFByb2JsZW0gKGNvbG9yaW5nIG1hcHMgc28gdGhhdCBhZGphY2VudCByZWdpb25zIGhhdmUKICAgICAgICBkaWZmZXJlbnQgY29sb3JzKSwgYW5kCiAgICA8bGk+dGhlIFRyYXZlbGluZyBTYWxlc21hbiBQcm9ibGVtICh2aXNpdGluZyBuIGNpdGllcyB3aXRoIG1pbmltdW0gY29zdCkuCjwvdWw+Cgo=

Final Exam

Zoom Meeting (Dec 16, 7:50am) Final Exam (Canvas Assignment)

Quick Links

Syllabus Timeline Textbook Homework Grades

Graph Theory

Can you find a walk that crosses each bridge once and exactly once?

Bridges

Color a map with n colors so that no two adjacent countries are colored the same. What is the least number n that works for any map? For the map of US Counties, you only need 4 colors:

Bridges

If the cost to travel between any 2 national parks in the USA is known what is the cheapest way to visit all of the parks exactly once?

One common theme shared by all of these problems is that they can be translated into problems involving a mathematical concept known as a graph.

Course Description

This is a introductory course on properties and applications of graphs. We will study graph-theoretic concepts such as paths, Eulerian circuits, trees, distance, matchings, connectivity, network flows, colorings, planarity, and spanning cycles. A primary goal is to improve students' clarity of thought and language when writing proofs in discrete mathematics.

Famous applications include:

the Minimum Connector Problem (building roads at minimum cost),
the Marriage Problem (matching men and women into compatible pairs),
the Assignment Problem (filling n jobs in the best way),
the Network Flow Problem (maximizing flow in a network of pipes),
the Committee Scheduling Problem (using the fewest time slots),
the Four Color Problem (coloring maps so that adjacent regions have different colors), and
the Traveling Salesman Problem (visiting n cities with minimum cost).