Graph Theory Syllabus

What is the degree sequence of a graph?

The list of vertex degrees, usually written in non-increasing order.

Distinguish between a walk, a trail, and a path in a graph.

A walk is any sequence of vertices connected by edges. A trail is a walk with no repeated edge. A path is a walk with no repeated vertex (hence no repeated edge).

Distinguish a circuit from a cycle.

A circuit is a closed trail (starts and ends at the same vertex, no repeated edge). A cycle is a closed path (no repeated vertices except the common start/end).

Define the length of a path and the girth of a graph.

The length of a path is its number of edges. The girth of a graph is the length of its shortest cycle (infinite if the graph is acyclic).

What is an Eulerian circuit, and what is the condition for its existence in a connected graph?

An Eulerian circuit is a closed trail using every edge exactly once. A connected graph has one if and only if every vertex has even degree.

What is the condition for a connected graph to have an Eulerian trail (path) that is not closed?

It has an Eulerian trail if and only if exactly two vertices have odd degree (the trail starts at one and ends at the other).

What is a Hamiltonian cycle?

A cycle that visits every vertex of the graph exactly once and returns to the start. (No simple necessary-and-sufficient condition is known for its existence.)

State Dirac's theorem for Hamiltonian cycles.

If $G$ is a simple graph with $n \geq 3$ vertices and every vertex has degree $\deg(v) \geq \frac{n}{2}$, then $G$ contains a Hamiltonian cycle.

When is a graph called connected?

When there is a path between every pair of vertices. A graph that is not connected is disconnected and splits into connected components.

Define a cut vertex (articulation point) and a bridge (cut edge).

A cut vertex is a vertex whose removal increases the number of connected components. A bridge is an edge whose removal increases the number of components.

Define vertex connectivity $\kappa(G)$ and edge connectivity $\lambda(G)$.

$\kappa(G)$ is the minimum number of vertices whose removal disconnects the graph (or reduces it to one vertex). $\lambda(G)$ is the minimum number of edges whose removal disconnects it.

State Whitney's inequality relating connectivity and minimum degree.

$$\kappa(G) \leq \lambda(G) \leq \delta(G),$$ where $\delta(G)$ is the minimum vertex degree.

In a directed graph, distinguish strongly connected from weakly connected.

Strongly connected: there is a directed path from every vertex to every other vertex. Weakly connected: the underlying undirected graph (ignoring directions) is connected.

Define the complete graph $K_n$ and give its number of edges.

$K_n$ is the simple graph on $n$ vertices in which every pair of distinct vertices is joined by an edge. It has $$\binom{n}{2} = \frac{n(n-1)}{2}$$ edges.

What is the degree of every vertex in $K_n$, and is $K_n$ regular?

Every vertex has degree $n - 1$, so $K_n$ is $(n-1)$-regular.

Define a bipartite graph.

A graph whose vertex set can be partitioned into two disjoint sets $X$ and $Y$ such that every edge joins a vertex in $X$ to a vertex in $Y$ (no edge lies within one part).

State the characterization of bipartite graphs in terms of cycles.

A graph is bipartite if and only if it contains no odd-length cycle. (Equivalently, it is $2$-colorable.)

Define the complete bipartite graph $K_{m,n}$ and give its number of edges.

$K_{m,n}$ has parts of sizes $m$ and $n$ with every vertex in one part joined to every vertex in the other. It has $m \cdot n$ edges.

Define a planar graph.

A graph that can be drawn (embedded) in the plane so that no two edges cross except at their shared endpoints.

State Euler's formula for connected planar graphs.

For a connected planar graph with $V$ vertices, $E$ edges, and $F$ faces (including the outer face): $$V - E + F = 2.$$

State the edge bound for a simple connected planar graph with $V \geq 3$ vertices.

$$E \leq 3V - 6.$$ For a simple bipartite (triangle-free) planar graph, $E \leq 2V - 4$.

State Kuratowski's theorem for planarity.

A graph is planar if and only if it contains no subgraph that is a subdivision of $K_5$ or of $K_{3,3}$.

Compare Breadth-First Search (BFS) and Depth-First Search (DFS) in traversal order and typical data structure.

BFS explores level by level (nearest vertices first) using a queue (FIFO). DFS explores as deep as possible before backtracking, using a stack or recursion (LIFO). Both run in $O(|V| + |E|)$ with adjacency lists.

Give one key application each of BFS and DFS.

BFS finds shortest paths (fewest edges) in an unweighted graph. DFS is used for detecting cycles, topological sorting, and finding connected/strongly connected components.

Describe Dijkstra's algorithm and its constraint and complexity.

A greedy single-source shortest-path algorithm that repeatedly selects the unvisited vertex of smallest tentative distance and relaxes its edges. It requires non-negative edge weights. With a binary heap it runs in $O((|V| + |E|) \log |V|)$.

How does the Bellman-Ford algorithm differ from Dijkstra's, and what is its complexity?

Bellman-Ford handles negative edge weights and can detect negative cycles. It relaxes all edges $|V| - 1$ times, running in $O(|V| \cdot |E|)$.

What does the Floyd-Warshall algorithm compute and what is its complexity?

It computes shortest paths between all pairs of vertices via dynamic programming, allowing negative edges (but no negative cycles). Its time complexity is $O(|V|^{3})$.

Define a minimum spanning tree (MST) of a connected weighted graph.

A spanning tree (a connected acyclic subgraph including all vertices) whose total edge weight is minimum among all spanning trees. It has exactly $|V| - 1$ edges.

Contrast Kruskal's and Prim's algorithms for finding an MST.

Kruskal's adds edges in increasing weight order, skipping any that form a cycle (uses a disjoint-set/union-find). Prim's grows a single tree from a start vertex, repeatedly adding the cheapest edge leaving the current tree (uses a priority queue).

Define the chromatic number $\chi(G)$ of a graph.

The minimum number of colors needed to color the vertices so that no two adjacent vertices share the same color (a proper vertex coloring).

Give the chromatic number of a bipartite graph (with at least one edge), a complete graph $K_n$, and a cycle $C_n$.

Bipartite (with an edge): $\chi = 2$. Complete graph: $\chi(K_n) = n$. Cycle: $\chi(C_n) = 2$ if $n$ is even, $3$ if $n$ is odd.

State the Four Color Theorem.

Every planar graph is $4$-colorable; that is, its vertices can be properly colored with at most $4$ colors, so $\chi(G) \leq 4$ for any planar $G$.

State the Max-Flow Min-Cut Theorem.

In a flow network, the maximum value of a flow from source $s$ to sink $t$ equals the minimum capacity over all $s$-$t$ cuts.

What does the Ford-Fulkerson method compute, and what does an augmenting path do?

It computes the maximum flow in a network by repeatedly finding an augmenting path (a source-to-sink path with residual capacity) and pushing flow equal to that path's bottleneck capacity until none remains.

Define when two graphs $G_1$ and $G_2$ are isomorphic.

When there exists a bijection $f: V(G_1) \to V(G_2)$ such that $u$ and $v$ are adjacent in $G_1$ if and only if $f(u)$ and $f(v)$ are adjacent in $G_2$ (adjacency is preserved).

List several graph invariants that must match for two graphs to be isomorphic.

Same number of vertices, same number of edges, identical degree sequences, same number of connected components, same girth, and matching cycle structure. Matching invariants are necessary but not sufficient for isomorphism.