# 1. Graph Basics

• graph: $G = (V, E)$ consists of vertices $V$ connected by edges $E$
• directed: edges have directions
• connected: there is a path between any two vertices
• adjacent/neighboring: two vertices with an edge between them
• degree: number of edges on a vertex in an undirected graph
• indegree/outdegree: number of edges going into and out of a vertex, respectively, in a directed graph
• path: sequence of edges connected by endpoints
• in this class paths are simple paths, which means vertices are not reused
• cycle: path that begins and ends on same vertex
• walk: sequence of edges connected by endpoints, which can be repeated
• tour: walk that begins and ends on same vertex

# 2. Planarity

• planar: a graph that can lie on a plane without edges crossing
• complete graph: $K_n$ graph on $n$ vertices where an edge exists between every pair
• $K_1$, $K_2$, $K_3$, and $K_4$ are planar
• $K_5$ is not planar
• complete bipartite graph: $K_{m,n}$ is a bipartite graph where an edge exists between every pair of vertices on different sides
• $K_{3,3}$ is not planar (it can be drawn on a donut without edges crossing)
• A graph containing $K_5$ or $K_{3,3}$ is not planar

# 3. Bipartite Graph

## Proof Structure

1. $$\text{bipartite} \Rightarrow \text{no tours of odd length}$$
• prove that if there is a tour, then it must have even length
2. $$\text{no tours of odd length} \Rightarrow \text{bipartite}$$
• prove that you can partition the vertices into two sets $L$ and $R$ such that within in each set, there are no edges