Simple Graph — Definition, Formula & Examples
A simple graph is a graph where each pair of vertices is connected by at most one edge, and no edge connects a vertex to itself. It is the most basic type of graph studied in discrete mathematics.
A simple graph consists of a nonempty set of vertices and a set of unordered pairs of distinct elements of , called edges. The conditions ensure that has no loops (edges from a vertex to itself) and no parallel edges (multiple edges between the same pair of vertices).
Key Formula
Where:
- = The number of vertices, $|V|$
- = The number of edges in the simple graph
Worked Example
Problem: Determine whether a graph on vertices {A, B, C, D} with edge set {(A,B), (A,C), (B,C), (C,D)} is a simple graph, and find the maximum number of edges it could have.
Check for loops: No edge connects a vertex to itself (e.g., no (A,A)), so there are no loops.
Check for parallel edges: Each pair of vertices appears at most once in the edge set. For instance, (A,B) is listed only once. So there are no multiple edges.
Compute maximum edges: With 4 vertices, the maximum number of edges in a simple graph is given by the formula.
Answer: The graph is a simple graph with 4 edges. The maximum possible number of edges on 4 vertices is 6 (which would be the complete graph ).
Why It Matters
Simple graphs are the default model in most graph theory courses and algorithms. When you study shortest paths, coloring, or network flow, the underlying structure is almost always assumed to be a simple graph unless stated otherwise. Recognizing this assumption helps you correctly apply degree-sum formulas and edge-count bounds.
Common Mistakes
Mistake: Assuming every graph is simple by default when the problem involves multigraphs or pseudographs.
Correction: A multigraph allows parallel edges and a pseudograph allows both parallel edges and loops. Always check the problem statement — if loops or repeated edges are present, the graph is not simple, and results like the maximum edge formula do not apply.