Graph types
Below is a compact catalog of graph types you will meet in discrete math and DSA. Wording varies by textbook—always match your course’s definition for “simple,” “regular,” and “Eulerian.” Cross-check with graph terminology.
Simple · Multigraph · Pseudograph · Undirected · Directed (digraph) · Weighted · Unweighted · Connected · Disconnected · Complete · Null · Regular · Cyclic · Acyclic · Tree · Forest · Bipartite · Complete bipartite · DAG · Planar · Non-planar · Sparse · Dense · Subgraph · Complement · Euler · Hamiltonian
1) Simple graph, multigraph, pseudograph
Simple graph
At most one edge between any two distinct vertices and no self-loops (this is the default “simple” undirected graph in many CS courses).
Multigraph
Parallel edges allowed between the same pair of vertices (same endpoints, repeated connections). Useful for multiple lanes, redundant links, or multiplicity counts.
Pseudograph
Self-loops allowed (an edge from a vertex to itself). Some authors also allow parallel edges in a pseudograph—read your text.
2) Undirected graph · Directed graph (digraph)
Undirected graph
Edges are unordered pairs {u, v}; adjacency is mutual. The adjacency matrix is symmetric (for the usual 0/1 encoding).
Directed graph (digraph)
Edges are ordered pairs (u, v) — an arc leaves u and enters v. Use in-degree / out-degree; reachability respects direction.
| Idea | Undirected | Directed |
|---|---|---|
| Adjacency matrix | Symmetric | Usually not symmetric |
| Degree | One number per vertex | In-degree and out-degree |
3) Weighted graph · Unweighted graph
Unweighted graph
Edges only indicate presence (or all cost 1). Shortest path often means fewest edges — commonly solved with BFS for single-source unweighted shortest paths.
Weighted graph
Each edge has a weight (distance, cost, time). Paths have length = sum of weights. Algorithms: Dijkstra, Bellman–Ford, Floyd–Warshall, etc., depending on constraints.
4) Connected graph · Disconnected graph
Connected graph
Undirected: exactly one connected component — every pair of vertices has a path.
Directed variants: strongly connected (mutual reachability along arcs) or weakly connected (connected if directions are ignored).
Disconnected graph
More than one connected component: at least two vertices lie in different components with no path between them (in the undirected sense).
5) Complete graph · Null graph · Regular graph
Complete graph
Denoted Kn: every pair of distinct vertices is adjacent. Simple undirected Kn has n(n−1)/2 edges.
Null graph
Also called an edgeless graph on n vertices: no edges (only isolated vertices). Same as the complement of Kn on those vertices; sometimes denoted Nn.
Regular graph
Every vertex has the same degree r — an r-regular graph (e.g. cycles are 2-regular; Kn is (n−1)-regular).
6) Cyclic graph · Acyclic graph
Cyclic graph
Contains at least one cycle (closed walk with distinct vertices in the simple-cycle sense; for digraphs, at least one directed cycle).
Acyclic graph
No cycles. Undirected: a forest (disjoint trees). Directed: see DAG below—acyclic directed graphs are the usual focus.
7) Tree · Forest
Tree
A connected acyclic undirected graph on n vertices with exactly n − 1 edges. Rooted trees add a distinguished root for parent/child—see Graph versus tree.
Forest
A disjoint union of one or more trees: acyclic undirected graph; not necessarily connected.
8) Bipartite graph · Complete bipartite graph
Bipartite graph
Vertices split into two independent sets L and R; every edge joins L to R. Equivalently: 2-colorable (for graphs with no self-loops).
Complete bipartite graph
Denoted Ka,b: every vertex in one part is adjacent to every vertex in the other part, with no edges within a part — total ab edges.
9) Directed acyclic graph (DAG)
DAG
A directed graph with no directed cycles. Used for prerequisite graphs and scheduling; vertices can be listed in topological order. Covered later in Topological sort.
10) Planar graph · Non-planar graph
Planar graph
Can be drawn in the plane so that edges meet only at shared endpoints (no crossings). Satisfies Euler’s formula for connected planar graphs: v − e + f = 2 (faces f).
Non-planar graph
Not planar — smallest classical examples are K5 and K3,3 (Kuratowski’s theorem characterizes obstructions in terms of subdivisions).
11) Sparse graph · Dense graph
Sparse graph
|E| is small relative to |V| (often O(|V|) or near-linear). Adjacency lists are typical in implementation.
Dense graph
Many edges—often |E| is Θ(|V|²) in worst case. An adjacency matrix can be acceptable when |V| is moderate. See Graph representation.
12) Subgraph · Complement graph
Subgraph
Formed by taking a subset of vertices and a subset of edges that only use those vertices and respect endpoints. Induced subgraph: all edges of the original graph between the chosen vertices.
Complement graph
On the same vertex set: two distinct vertices are adjacent iff they are not adjacent in the original simple graph. The union of G and its complement (on the same vertices) is a complete graph (for simple graphs without loops).
13) Euler graph · Hamiltonian graph
Euler graph (Eulerian graph)
Usually means: the graph has an Euler circuit — a closed walk using every edge exactly once. For a connected undirected simple graph, this holds iff every vertex has even degree. (Euler trail variants allow exactly two odd-degree vertices as endpoints.)
Hamiltonian graph
Contains a Hamiltonian cycle: a cycle that visits every vertex exactly once (except start = end). No simple degree test like Euler’s; checking is computationally hard in general (NP-complete).
Note: Directed analogues (Eulerian digraphs, Hamiltonian cycles in digraphs) use similar ideas with in/out-degree conditions for Euler trails in strongly connected settings.
Key takeaway
Identify which types above apply (simple? directed? weighted? DAG?) before picking representation and algorithms — mismatched assumptions (parallel edges, negative weights, planarity) break correctness or complexity proofs.
Next up: Graph traversal overview · Graph representation · BFS on graphs