AMS 301 Study Guide - Midterm Guide: Hamiltonian Path, Eulerian Path, Planar Graph

• School: Stony Brook University
• Department: Applied Mathematics and Statistics
• Course: AMS 301
• Professor: Zhenhua Liu

Document Summary

Isomorphism: one to one correspondence between vertices in g and g", adjacent vertices must correspond as well. If graphs are isomorphic, subgraphs must be isomorphic too. Edge cover: count degrees, count edges, find lower bound. Sum of the degree of all vertices is equal to twice the number of edges. A graph g is bipartite if its vertices set v can be divided into v1 and v2 such that every edge joins a vertex in v1 with a vertex in v2. Testing planar graphs the circle-chord method: 1. Find a circuit that contains all the vertices. (what if there is no such circuit?) The remaining edges not one the circuit are called chords. Randomly choose a chord and put it outside the circle. The chosen chord will force some other chord to be inside the circle. The inside chords will further force other chord to be outside the circle. Euler cycle: all vertices must have even degree.