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.