# 1. Graph Basics

**graph**: consists of vertices connected by edges
**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**: graph on vertices where an edge exists between every pair
- , , , and are planar
- is not planar

**complete bipartite graph**: is a bipartite graph where an edge exists between every pair of vertices on different sides
- is not planar (it can be drawn on a donut without edges crossing)

- A graph containing or is not planar

# 3. Bipartite Graph

## Proof Structure

- \( \text{bipartite} \Rightarrow \text{no tours of odd length} \)
- prove that if there is a tour, then it must have even length

- \( \text{no tours of odd length} \Rightarrow \text{bipartite} \)
- prove that you can partition the vertices into two sets and such that within in each set, there are no edges