Graph Types

Regular Graphs

A graph is $k$-regular if every vertex has degree $k$.

Examples

• 0-regular: isolated vertices
• 1-regular: perfect matching
• 2-regular: disjoint cycles
• 3-regular: cubic graph
• Complete graph $K_n$: $(n-1)$-regular

Properties

For a $k$-regular graph with $n$ vertices: $|E| = \frac{kn}{2}$

Bipartite Graphs

A graph is bipartite if vertices can be partitioned into two sets $U$ and $V$ such that every edge connects a vertex in $U$ to one in $V$.

Characterization

A graph is bipartite if and only if it contains no odd cycles.

Testing Bipartiteness

Use BFS/DFS with 2-coloring. If no conflicts arise, graph is bipartite.

Complete Bipartite Graph $K_{m,n}$

Every vertex in the first set (size $m$) is connected to every vertex in the second set (size $n$).

• Edges: $mn$
• Bipartite with parts of sizes $m$ and $n$

Special case: $K_{1,n}$ is a star graph.

Trees

A tree is a connected graph with no cycles.

Equivalent Definitions

For a graph $G$ with $n$ vertices, the following are equivalent:

1. $G$ is a tree
2. $G$ is connected and has $n - 1$ edges
3. $G$ has no cycles and has $n - 1$ edges
4. There is exactly one path between any two vertices
5. $G$ is connected, but removing any edge disconnects it
6. $G$ has no cycles, but adding any edge creates exactly one cycle

Properties

• $|E| = |V| - 1$
• At least 2 leaves (vertices of degree 1) if $|V| \geq 2$
• Adding one edge creates exactly one cycle

Rooted Trees

A rooted tree has a designated root vertex.

Terminology

• Parent: The neighbor closer to the root
• Child: A neighbor farther from the root
• Ancestor/Descendant: Generalization of parent/child
• Leaf: Vertex with no children
• Internal vertex: Vertex with at least one child
• Depth: Distance from root to vertex
• Height: Maximum depth of any vertex

Binary Trees

Each vertex has at most 2 children (left and right).

Types

• Full binary tree: Every internal vertex has exactly 2 children
• Perfect binary tree: All leaves at same depth, all internal vertices have 2 children
• Complete binary tree: All levels filled except possibly the last, which is filled left-to-right

Properties of Full Binary Trees

With $i$ internal vertices and $l$ leaves:

• $l = i + 1$
• Total vertices: $n = 2i + 1$

Properties of Perfect Binary Trees

With height $h$:

• Leaves: $2^h$
• Internal vertices: $2^h - 1$
• Total vertices: $2^{h+1} - 1$

Forests

A forest is a graph with no cycles (disjoint union of trees).

For a forest with $n$ vertices, $c$ connected components: $|E| = n - c$

Planar Graphs

A graph is planar if it can be drawn in the plane without edge crossings.

Euler's Formula

For a connected planar graph: $|V| - |E| + |F| = 2$

where $F$ is the number of faces (including unbounded outer face).

Degree-Face Bound

$|E| \leq 3|V| - 6 \quad \text{(for } |V| \geq 3 \text{)}$

Non-Planar Examples

• $K_5$ (complete graph on 5 vertices)
• $K_{3,3}$ (complete bipartite graph)

Connected Graphs

A graph is connected if there's a path between every pair of vertices.

Connected Components

Maximal connected subgraphs. Every graph is a disjoint union of its components.

Strongly Connected (Digraphs)

A directed graph is strongly connected if there's a directed path between every pair of vertices in both directions.

Weakly Connected (Digraphs)

Connected if we ignore edge directions.

Special Graph Families

Petersen Graph

A famous 3-regular graph with 10 vertices.

• Not planar
• Hamiltonian
• Vertex-transitive

Grid Graphs

Vertices at integer coordinates, edges between adjacent points.

• $m \times n$ grid has $mn$ vertices and $2mn - m - n$ edges

Hypercube $Q_n$

Vertices are $n$-bit strings.

• $Q_1$: single edge
• $Q_2$: square
• $Q_3$: cube
• $|V| = 2^n$, $|E| = n \cdot 2^{n-1}$

Circulant Graphs

Vertices $0, 1, \ldots, n-1$ on a circle. Connection set $S$: edge $(i, j)$ if $|i - j| \mod n \in S$.