1
A graph is a relation, drawn
Sets, Relations, and Functions's symmetric irreflexive relation on V is exactly a simple graph. The picture adds nothing mathematically and a great deal practically.
Lesson · Graphs and Trees · Basics
Graphs and Graph Models
A graph is a set of vertices and a set of edges joining them. The definition is deliberately spare, which is why the same object models networks, dependencies, molecules and schedules.
G = (V, E) V vertices, E edges (pairs of vertices)
simple graph: no loops, no repeated edges, undirected
adjacent: joined by an edge incident: vertex meets edge
a GRAPH is not a plot
The definition
Core ideas
What this lesson establishes
The definition is short and the variants matter: what counts as an edge decides which theorems apply.
2
The drawing is not the graph
Position and edge shape carry no information. Two very different pictures can be the same graph, which is “Subgraphs and Graph Isomorphism”'s subject.
3
The variants are not interchangeable
Loops, multiple edges and directions each change which theorems hold. "Simple graph" is the default here and is stated where it matters.
The material
What a graph is
The definition, the variants, and four models.
Definition · Simple graph
A simple graph G = (V, E) is a finite set V of vertices together with a set E of edges, each an unordered pair of distinct vertices. No loops and no repeated edges.
Two vertices joined by an edge are adjacent or neighbours; a vertex and an edge meeting are incident. |V| is the order and |E| the size.
variant edges may… example use
simple graph neither loop nor repeat friendship
multigraph repeat road networks with
parallel routes
pseudograph loop and repeat state machines
directed graph have a direction dependencies, the web
weighted graph carry a number distances, costs
Unless stated otherwise, "graph" on this course means a simple undirected graph. “Shortest Paths and Dijkstra's Algorithm” and “Spanning Trees and Minimum Spanning Trees” attach weights; directions appear only in remarks.
Standard families
Kₙ complete graph every pair joined C(n,2) edges
Cₙ cycle a single closed ring n edges
Pₙ path a single open chain n−1 edges
K_{m,n} complete bipartite every left–right pair mn edges
Qₙ hypercube bit strings differing n·2^{n−1} edges
in one position
K₅ and K_{3,3} matter later: “Planar Graphs and Euler's Formula” shows they are precisely the obstructions to drawing a graph in the plane without crossings.
Four models
- Social networks. Vertices are people, edges are acquaintance. Sets, Relations, and Functions's pigeonhole result — two people share a degree — is a statement about this graph.
- Road networks. Vertices are junctions, edges are roads, weights are distances. Shortest paths are “Shortest Paths and Dijkstra's Algorithm”.
- Dependencies. Vertices are tasks, directed edges are "must precede". A valid schedule exists exactly when there is no cycle, which is Sets, Relations, and Functions's partial order again.
- Molecules. Vertices are atoms, edges are bonds. Two molecules with the same formula and different structures are non-isomorphic graphs, which is “Subgraphs and Graph Isomorphism”.
The common thread: whenever the data is "a set of things and which pairs are related", it is a graph, and every theorem in this course applies to it at once. That generality is the reason graph theory is worth a course.
Theorem · Maximum edges
A simple graph on n vertices has at most C(n,2) = n(n−1)/2 edges, with equality exactly for Kₙ.
Each edge is an unordered pair of distinct vertices, and no pair may repeat, so the edges form a subset of the C(n,2) pairs. “Combinations” in Combinatorics and Counting counts them.
□
Interactive
Graph workbench
Your graph, the course's algorithms
Method
Modelling with a graph
Vertices first, then decide what an edge means.
1
Say what a vertex is
One per entity: person, junction, task, atom. If the answer is unclear the model is not ready.
2
Say exactly what an edge means
"Have met", "a road exists", "must precede". The relation must be checkable for every pair.
3
Decide the variant
Symmetric relation: undirected. Asymmetric: directed. Repeated connections: multigraph. Costs: weighted.
4
Restate the question in graph terms
"Can everyone be reached" is connectivity; "is there a route using every road once" is an Euler circuit. The translation is where the theorems become available.
Graphs
Score 0 / 0Choose the answer you can justify.
Counting edges in the standard families
Each count is a small application of Combinatorics and Counting.
Kₙ every pair joined C(n,2) = n(n−1)/2
K₅ has 10 edges, K₁₀ has 45
Cₙ a closed ring n edges, every degree 2
Pₙ an open chain of n vertices n−1 edges
K_{m,n} every left vertex joined to every right one m·n edges
K_{3,3} has 9 edges
Qₙ vertices = bit strings of length n (2ⁿ of them)
edges join strings differing in one bit
each vertex has degree n, so |E| = n·2ⁿ/2 = n·2^{n−1}
The hypercube count used the handshake theorem of “Degree and the Handshake Theorem” before it was stated: 2|E| = Σ deg(v) = n · 2ⁿ. Counting edges through degrees is the standard move and it is worth having early.
Common mistakes
1
Reading a graph as a plotThe word means two different things. A graph here is vertices and edges; nothing is being plotted.
2
Treating the drawing as the objectPosition and edge curvature carry no information. Two unrecognisably different pictures can be the same graph.
3
Using an undirected graph for an asymmetric relation"Follows" and "must precede" both need direction. Dropping it discards the information the model existed to carry.
Check your understanding
✓
Finish when you can state what a vertex and an edge are before anything else.
Model "which pairs of countries share a land border" as a graph. Say what the vertices are, what an edge means, and whether the graph is simple — then ask what the degree of a vertex tells you.
Note: Graph theory begins with Euler's 1736 paper on the bridges of Königsberg, which “Euler and Hamilton Paths” revisits. He solved it by discarding the map entirely and keeping only which land masses were connected — the first abstraction of this kind.