Course contentsShow
← Computer Science
Lesson 660 of 2,87216. Graphs: Representation and Basic ConceptsFree lesson

Simple Graphs and Multigraphs

Distinguish between graphs with at most one edge per vertex pair versus those allowing multiple edges or loops.

Simple Graphs and Multigraphs

What you'll learn: You'll understand the difference between graphs that allow at most one edge between any two vertices versus graphs that permit multiple edges or self-loops.

The Core Distinction

Now that you understand graphs have vertices and edges, it's time to learn that not all graphs follow the same rules about connections.

A simple graph is the most restricted type: between any pair of vertices, there can be at most one edge, and vertices cannot have edges to themselves (no loops). Think of this like a professional network where you're either connected to someone or you're not—there's no concept of being "double-connected."

A multigraph relaxes these restrictions: it allows multiple edges between the same pair of vertices, and some variants permit self-loops (edges from a vertex back to itself).

Real-World Analogy

Imagine a city transportation map:

  • Simple graph: A map showing whether two cities are connected by any road. Either there's a connection or there isn't.
  • Multigraph: A realistic map showing that two cities might be connected by multiple highways, a train line, and a ferry route—each represented as a separate edge.

Similarly, a flight network is a multigraph because airlines often run multiple daily flights between major cities (multiple edges), and a self-loop could represent a scenic tour flight that departs and returns to the same airport.

Why It Matters

The distinction affects how you implement and traverse graphs. Simple graphs are easier to represent (you only track whether an edge exists), while multigraphs require counting or distinguishing between multiple connections.

Key Takeaway: Simple graphs allow at most one edge per vertex pair with no self-loops, while multigraphs permit multiple edges between vertices and sometimes self-loops.