Foundations — Graph definitions — directed, undirected, weighted, unweighted, simple, multigraph

This page assumes nothing. Before you touch the parent note, we build every symbol it uses — one at a time, each anchored to a picture — so that when you meet $G=(V,E)$, $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$, or ${\sum }_v\mathrm{deg}(v)=2m$, no symbol is a stranger.

Symbol 0 — A "set" and how we write it

Everything in graphs is built from sets, so we start there.

The picture: think of a shopping bag with three fruits in it. It doesn't matter which fruit you put in first, and you can't have "the same apple twice" — it's just in the bag or not.

Why the topic needs it: a graph is a pair of sets — one bag of dots, one bag of lines. Everything else is decoration on top of these two bags.

Symbol 1 — Vertices, and the dot picture

The picture — three dots, nothing joining them yet:

Look at the figure: three lavender dots labelled $A$, $B$, $C$. The bag holding them is written $V=\{A,B,C\}$. That's all a vertex is — a labelled point.

Why the topic needs it: vertices are the things being connected. Friends, cities, web pages — whatever your real problem is, each "thing" becomes one dot.

Symbol 2 — The size bars $|V|$ and the letter $n$

The picture: just count the dots. In the figure above, $|V|=3$, so $n=3$.

Why the topic needs it: almost every formula ("max edges", "how slow is this algorithm?") is written in terms of $n$, so we need a name for "how many dots."

Symbol 3 — A pair, ordered vs unordered

This is the single most important distinction on the whole page, so we build it slowly.

The picture — a plain line vs an arrow:

On the left, a plain mint line between $u$ and $v$: no head, so you can't tell "which direction" — that is the unordered pair $\{u,v\}$. On the right, a coral arrow from $u$ to $v$: the head marks a direction, so $(u,v)$ and $(v,u)$ are genuinely different pictures.

Why the topic needs it: an edge is a pair of vertices. Whether it's ordered or unordered is precisely what makes a graph directed or undirected.

Symbol 4 — Edges, and the set $E$; the letter $m$

The picture — take the three dots and actually connect two of them:

Here we drew one line between $A$ and $B$. So $E=\{\{A,B\}\}$ (a bag holding a single unordered pair), and $m=|E|=1$.

Why the topic needs it: edges are the relationships. Without them you just have loose dots; the whole point of a graph is which dots are connected.

Symbol 5 — The graph itself, $G=(V,E)$

Now we can read the master notation.

The picture: the whole drawing (all dots + all lines) is $G$. The two bags $V$ and $E$ together describe it completely.

Why the topic needs it: this is the definition the parent note opens with. Everything after it — directed, weighted, simple — is just a rule about what's allowed to live inside $E$.

Symbol 6 — Weight, the function $w(u,v)$

The picture: imagine each line has a little tag pinned to it, like "\400$"onaflightor"5km"onaroad.An\ast unweighted\ast graphisthespecialcasewhereyoudo{n}^{\prime }tbotherwritingtags(equivalently,everytagsays$1$).

Why the topic needs it: "how many hops?" ignores weight; "cheapest route?" needs it. The weight is what separates a BFS problem from a Dijkstra problem.

Symbol 7 — Degree, and the sum symbol $\sum$

The picture — stand on one dot and count the lines leaving it:

In this figure, $\mathrm{deg}(A)=2$ (two lines leave $A$), $\mathrm{deg}(B)=2$, $\mathrm{deg}(C)=1$, $\mathrm{deg}(D)=1$. Notice each line got counted once at each of its two ends.

Why the topic needs it: the Handshaking Lemma ${\sum }_v\mathrm{deg}(v)=2m$ (see Handshaking lemma and degree sequences) says this total is always twice the number of edges — because every edge, having two ends, is counted twice. In our figure $m=3$, and indeed $6=2\times 3$. ✓

Symbol 8 — "$n$ choose $2$", the notation $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$

Why that formula, step by step:

The picture: every possible unordered pair of distinct dots is one possible line. Counting them = counting the most lines a simple undirected graph can have.

Why the topic needs it: this is exactly the "maximum edges" formula, and it's the size of the complete graph $K_n$.

How these foundations feed the topic

Where these lead next

Once the symbols above feel automatic, the natural next stops are: storing a graph in memory via Graph representations — adjacency list vs matrix, walking it hop-by-hop with BFS — breadth first search, finding cheapest paths with Dijkstra's algorithm, ordering dependencies with Topological sort, and the special "no-cycle" graphs called Trees as special graphs.

Equipment checklist

Test yourself — each line reveals the answer.