STOR 215: Study Guide for the Final Exam

Combine Study Guides for Midterms 1 and II with the following

Basic definitions for graphs: vertex, edge, directed and undirected graphs, adjacency of vertices

Special graphs: complete graphs, cycles, bipartite graphs

Degree: Handshaking theorem and corollaries

Subgraphs and unions of graphs

Complete matching, perfect matching, and Hall's marriage theorem

Adjacency matrices and edge lists

Graph isomorphism: definition and invariants

Connected graphs: paths and circuits/cycles, connected components

Counting paths between vertices using the adjacency matrix

Euler circuits and Euler paths

Hamilton circuits and paths

Weighted graphs, shortest path problem, Dykstra's algorithm

Planar graphs and planar representations

Euler's formula and corollaries

Kuratowski's theorem characterizing planar graphs