Instagram follows are directed. WhatsApp friends are not.
A tree lets one node connect to several children, but never back to a cousin or an ancestor out of order. A graph drops every restriction — any node can connect to any other, in either direction.
After this lesson
You should be able to
- Define a graph in terms of vertices and edges.
- Distinguish a directed graph from an undirected one.
- Explain why a tree is a graph with extra restrictions, not a separate structure.
Following someone is not the same as being followed
You can follow a celebrity on Instagram without them following you back — the connection points one way. A graph that models this is directed: an edge from A to B does not imply an edge from B to A. Your WhatsApp friend list works differently — if you are in someone's contacts as a friend, the relationship is naturally mutual, which an undirected graph models: an edge between A and B means the connection runs both ways.
A graph is simply a set of vertices (the things — people, cities, web pages) and a set of edges connecting pairs of them (the relationships — follows, roads, links). That is the entire definition. Everything else in this unit is about what you can compute once you have one.
Vocabulary you already half-know
Two vertices joined by an edge are adjacent. The degree of a vertex is how many edges touch it — in a directed graph, this splits into in-degree (edges pointing in, your follower count) and out-degree (edges pointing out, how many accounts you follow). A path is a sequence of edges connecting one vertex to another; a cycle is a path that returns to where it started.
A tree was a graph all along
Every tree from Unit II is a graph with three extra rules bolted on: it is connected (every vertex reachable from every other), it has no cycles, and it has one designated root. Remove those restrictions and you get the general graphs this unit studies — a network with no required shape at all, where any vertex may connect to any number of others in any pattern, cycles included.
This is worth sitting with: nothing you learn about graphs contradicts Unit II. It generalizes it. A graph traversal algorithm applied to a tree still works — a tree simply never gives it a cycle to worry about.
Tree (Unit II): General graph (this unit):
A A --- B
/ \ \ /
B C \ /
| C --- D
D /
E
/* Tree: connected, no cycles, one root.
Graph: none of those rules required. */Try it yourself
Model your own Instagram-style follow network for four friends where at least one follow is one-directional and at least one is mutual. Draw it and list its edges as (from, to) pairs.
Need a hint?
A mutual follow needs two separate directed edges, one each way — not one undirected edge.
Check the worked solution
A mutual follow between P and Q is represented as two directed edges, (P, Q) and (Q, P), both present — not collapsed into one, because a directed graph has no built-in idea of 'both ways' the way an undirected graph does. This distinction matters the moment you write code: an undirected edge is stored once and read both ways; a directed 'mutual' relationship is genuinely two separate edges that happen to both exist.
Quick check
Why does an Instagram-style follow relationship need a directed graph rather than an undirected one?
Why this lesson exists
Syllabus mapping
Introduction · Directed Graphs
Maps to course outcomes CO1, CO4.