Categories of Graphs and Their Properties

1. Complete Graphs

A complete graph $K_n$ is an undirected graph with $n$ vertices where every pair of distinct vertices is connected by exactly one edge.

Properties

• Number of edges: $\dfrac{n(n-1)}{2}$
• Every vertex has degree $n - 1$
• For $n = 4$: 6 edges; for $n = 5$: 10 edges

Significance

Complete graphs represent the worst-case scenario for many algorithms — every possible connection exists. The Travelling Salesman Problem considers complete weighted graphs.

KEY TAKEAWAY: $K_n$ has the maximum possible number of edges for $n$ vertices: $\dfrac{n(n-1)}{2}$.

2. Connected Graphs

A connected graph is an undirected graph in which there is a path between every pair of vertices.

Properties

• No isolated vertices (every vertex can reach every other vertex)
• Removing certain edges or vertices may disconnect the graph

Strongly vs. Weakly Connected (Directed Graphs)

Why It Matters

• Prim’s algorithm requires a connected graph to produce a spanning tree.
• BFS/DFS from a single source only reaches all vertices in a connected graph.

3. Directed Acyclic Graphs (DAGs)

A DAG is a directed graph with no directed cycles.

Properties

• Has a topological ordering — vertices can be arranged so all edges point “forward”
• Can model dependencies (task A must precede task B)

Applications

• Task scheduling / project management (prerequisite tasks)
• Build systems (file compilation order)
• Decision trees and state graphs for planning
• Dynamic programming problems (subproblem dependency structure)

  Compile A → Link A
  Compile B → Link A → Package

EXAM TIP: If a directed graph has a cycle, it cannot be a DAG and cannot be topologically sorted. Look for cycles when justifying whether a graph is a DAG.

4. Trees

A tree is a connected, undirected, acyclic graph.

Properties

• $n$ vertices → exactly $n - 1$ edges
• Exactly one path between any two vertices
• Removing any edge disconnects the graph
• Adding any edge creates a cycle

Rooted Trees

A tree with one designated root vertex. Vertices are called parents/children/leaves. Used in decision trees, parse trees, and binary search trees.

Spanning Trees

A spanning tree of a connected graph $G$ includes all $n$ vertices and exactly $n-1$ edges (no cycles). The minimum spanning tree (MST) is the spanning tree with minimum total weight — found by Prim’s algorithm.

Summary Comparison

VCAA FOCUS: Know the formal definitions and be ready to classify a given graph into one or more categories. Properties (number of edges, connectivity, cycle-free) are frequently tested.