Graphs and Basic Definitions

Graphs, in the precise sense defined here, are the substrate for an enormous range of applications. In computer science, graphs model computer networks (vertices = machines, edges = links), the World Wide Web (vertices = pages, edges = hyperlinks — naturally directed and possibly with loops, since pages can link to themselves), and dependency structures in compilers and build systems. In operations research and engineering, graphs represent transportation and logistics networks, where multigraphs are essential because multiple distinct routes between the same two locations are common, exactly as in the worked bus-route example above. In chemistry, molecular structure diagrams are graphs whose vertices are atoms and whose edges are bonds; double and triple bonds are naturally modeled with parallel edges (a multigraph). In social science and epidemiology, graphs model acquaintance and contact networks, with adjacency encoding a direct relationship (friendship, contact) that then feeds into models of information spread or disease transmission. In cryptography and complexity theory, hardness of certain graph problems (like finding large cliques, related to the complete-graph notion $K_n$ introduced above) underlies security assumptions and complexity-class separations. In statistics and machine learning, graphical models encode conditional independence structure among random variables using vertices for variables and edges for direct dependencies. All of these applications depend on the basic distinctions made rigorous here: what counts as a vertex versus an edge, whether loops or parallel edges are permitted, and the sharp separation between a graph's combinatorial identity and any particular drawing of it — distinctions that become indispensable once one studies Degree and the Handshake Lemma and, later, Graph Isomorphism.

Ask the tutor: Can you walk through how the definition of a graph changes once we allow edges to be directed, and how adjacency then splits into "in-neighbor" and "out-neighbor"?

Think of a graph as the abstract skeleton of a network. The vertices are the "things" — people, cities, atoms, web pages — and the edges record which pairs of things are directly related. Crucially, a graph carries no information about position, distance, or order beyond the bare adjacency data: if you redraw the dots anywhere in the plane and redraw the connecting curves anywhere between them, as long as the same pairs of dots are joined, it is the same graph. This is why we insist on the set-theoretic definition rather than a picture. A picture is a witness, or a convenient encoding, but the mathematical object is the pair $(V,E)$. For instance the vertex set $V = \{1,2,3,4\}$ with edge set $E = \{\{1,2\},\{2,3\},\{3,4\},\{4,1\}\}$ is a 4-cycle no matter whether you draw it as a square, a bowtie-looking self-crossing shape, or a wobbly quadrilateral — the combinatorics is identical. Adjacency is symmetric ($u$ adjacent to $v$ iff $v$ adjacent to $u$, since $\{u,v\} = \{v,u\}$ as sets) and it is a relation between vertices, while incidence is a relation between a vertex and an edge. Keeping these two words distinct avoids a huge amount of confusion later, especially once directed graphs and hypergraphs enter the picture. The step from simple graphs to multigraphs (allowing parallel edges) and graphs with loops is motivated by real modeling needs: two cities might be joined by several distinct flight routes (parallel edges), and a web page might link to itself (a loop). The formal device — an auxiliary function $\varphi$ from a set of edge names to the set of vertex pairs (or single vertices) — is what lets us have two different edges "look the same" as a pair $\{u,v\}$ while remaining genuinely distinct objects of the edge set $E$.

Proof of corollary. Immediate from the theorem's counting argument: $E$ ranges freely over all subsets of the $\binom{n}{2}$-element set $\binom{V}{2}$, and a finite set with $m$ elements has exactly $2^m$ subsets (each of the $m$ elements is independently included or excluded). $\blacksquare$

Example 1 — a graph modeling a genuinely asymmetric situation. Consider a small collaboration network among five researchers, labeled by their initials:

Suppose the co-authorship data is: $A$ has written with $B$ and with $D$; $B$ has written with $A$, with $C$, and with $E$; $C$ has written with $B$ and with $D$; $D$ has written with $A$ and with $C$; $E$ has written with $B$ only. Encoding "has written with" as an edge, we get

Note $|E(G)| = 5$. Let us verify this is consistent and extract basic data. Degrees. Count incidences at each vertex:

• $\deg(A)$: $A$ appears in $\{A,B\}$ and $\{A,D\}$, so $\deg(A) = 2$.
• $\deg(B)$: $B$ appears in $\{A,B\}, \{B,C\}, \{B,E\}$, so $\deg(B) = 3$.
• $\deg(C)$: $C$ appears in $\{B,C\}, \{C,D\}$, so $\deg(C) = 2$.
• $\deg(D)$: $D$ appears in $\{A,D\}, \{C,D\}$, so $\deg(D) = 2$.
• $\deg(E)$: $E$ appears only in $\{B,E\}$, so $\deg(E) = 1$.

Sum of degrees: $2+3+2+2+1 = 10 = 2 \cdot |E(G)|$, consistent with the fact (foreshadowing the Handshake Lemma) that the sum of all degrees always equals twice the number of edges, since each edge contributes exactly $1$ to the degree of each of its two distinct endpoints. Checking the bound of the theorem. Here $n = 5$, so $\binom{5}{2} = 10$. Indeed $|E(G)| = 5 \le 10$, consistent with the theorem, and $G$ is far from complete: e.g. $\{A,C\} \notin E(G)$ ($A$ and $C$ never co-authored), $\{A,E\} \notin E(G)$, $\{D,E\} \notin E(G)$. Precisely $10 - 5 = 5$ pairs are non-edges, matching $|\binom{V}{2} \setminus E(G)| = 5$. Adjacency vs. incidence, made concrete. $B$ and $C$ are adjacent (joined by the edge $\{B,C\}$). The edge $\{B,C\}$ is incident to $B$ and incident to $C$; it is not incident to $A$, $D$, or $E$. The edges $\{A,B\}$ and $\{B,C\}$ are adjacent edges, since they share the single endpoint $B$; the edges $\{A,D\}$ and $\{B,C\}$ are not adjacent, since they share no endpoint.

Example 2 — a multigraph with a loop, showing where the extra structure is needed. A small city has bus routes connecting four terminals $V = \{P, Q, R, S\}$. Route data: there are two distinct express routes both running nonstop between $P$ and $Q$ (different companies, same two terminals); there is one route between $Q$ and $R$; there is a circular sightseeing tour that departs from $R$ and returns to $R$ without stopping elsewhere (a loop at $R$); and there is one route between $R$ and $S$. Vertex $P$ additionally has no route to $S$ or to $R$ directly. This cannot be modeled as a simple graph, because a simple graph's edge set is a set of pairs, so it cannot record "two distinct routes between the same pair of terminals," nor can $\{u,v\}$ with $u=v$ ever occur (a simple graph's edges are $2$-element subsets, which by definition have two distinct elements). We use the multigraph definition instead. Let the edge-label set be

with assignment function $\varphi$ given by

Here $e_1 \ne e_2$ are parallel edges, since $\varphi(e_1) = \varphi(e_2) = \{P,Q\}$ but they are different elements of $E$ (different bus companies). $e_4$ is a loop at $R$, since $\varphi(e_4) = R$ is a single vertex. Degree computation, carefully. Using the multigraph degree definition (ordinary incidences count once, loops count twice):

• $\deg(P)$: $P$ is an endpoint of $e_1$ and $e_2$ (each ordinary), so $\deg(P) = 2$.
• $\deg(Q)$: $Q$ is an endpoint of $e_1, e_2, e_3$, so $\deg(Q) = 3$.
• $\deg(R)$: $R$ is an endpoint of $e_3$ (ordinary, contributes $1$), $e_4$ (loop, contributes $2$), and $e_5$ (ordinary, contributes $1$); so $\deg(R) = 1 + 2 + 1 = 4$.
• $\deg(S)$: $S$ is an endpoint of $e_5$ only, so $\deg(S) = 1$.

Sum of degrees: $2 + 3 + 4 + 1 = 10 = 2 \cdot |E| = 2 \cdot 5$. This again matches the handshake-style identity, provided loops are counted with weight $2$ — which is exactly why the convention is set up that way: it preserves "sum of degrees $=$ twice the number of edges" even in the presence of loops and parallel edges. If we had (incorrectly) counted the loop $e_4$ with weight $1$, we would get degree sum $9 \ne 10$, breaking the identity — a good sanity check for why the weight-$2$ convention for loops is the "correct" one, not an arbitrary choice.