AMS 301 Cheat Sheet – Midterm 1 (Sept. 29th) | Download for quality grades |

Document Content and Description Below

Terminology: 1. Connected Graph: There is a path (NOT edge) between every pair of vertices. 2. Isomorphism: There exists one-to-one correspondence in two isomorphic graphs. 3. Sub-graph: Formed by ... a subset of vertices and edges. 4. Complete Graph: Each vertex is adjacent to all other vertices. (Notation: Kn) 5. Graph Components: A component H of a graph G is a connected sub-graph of G. Besides, there is no path between any vertex in H and any vertex not in H. 6. Bipartite Graph: Every circuit in G has even length. Set of all vertices V can be divided into V1 and V2 such that every edge joins a vertex in V1 with vertex in V2. 7. Planar Graph: A graph can be drawn on a plane without edge crossing. 8. Euler Trail: A path with no repeated edges and contains all the edges in the graph. 9. Euler Cycle: a cycle that contains all edges in a graph. 10. Multi-graph: multiple edges connecting the same pair of vertices. 11. Hamilton Circuit: A circuit that visits each vertex exactly once. Theorem: 1. Edge Counting: In any graph, the sum of all vertices degree = 2 * (# of edges) 2. Kuratowski’s Theorem: A graph is planar if and only if it does not contain a sub-graph that is K5 or K3,3. 3. Euler’s Theorem 1: If G is a connected planar graph, then any plane depiction of G must have r = e – v + 2 regions. (e = # of edges, v = # of vertices) 4. Euler’s Theorem 2: A multi-graph has an Euler cycle if and only if it is connected and has all vertices of even degree. 5. Edge Vertices Rule: If G is a c [Show More]

Last updated: 1 year ago

Preview 1 out of 2 pages