A graph G = (V, E) consists of a set of vertices V and a set of edges E, where each edge connects two vertices. Key concepts include vertex degree (the number of edges incident to a vertex), the handshaking lemma (the sum of all degrees equals twice the number of edges), and the distinction between simple graphs (no loops or multiple edges), multigraphs, and directed graphs (digraphs). Graphs model an enormous range of phenomena: social networks, road maps, circuit layouts, and dependency structures.
Draw graphs by hand constantly. Start with small examples (5-6 vertices), identify degrees, count edges, and verify the handshaking lemma numerically. Move between visual drawings and formal set notation to build fluency with both representations.
Graph theory begins with a deceptively simple idea: take a set of objects (vertices) and a set of pairwise relationships between them (edges). Formally, a graph G = (V, E) is just these two sets. Despite this minimalism, graph theory captures the structure of an enormous range of real-world systems — social networks, road maps, the internet, molecular bonds, and prerequisite relationships like those in this knowledge graph.
A key concept to internalize early is that a graph is a *combinatorial* object, not a geometric one. When you draw a graph on paper, the positions of the vertices and the curves of the edges are irrelevant. What matters is which vertices are connected by edges. Two drawings that look completely different can represent the exact same graph. This means your intuitions about geometry (distance, area, crossing) do not directly apply — you have to reason purely from the adjacency relationships.
The *degree* of a vertex is the number of edges incident to it. In a social network, degree is how many friends someone has. The *handshaking lemma* says that the sum of all vertex degrees equals twice the number of edges: Σ deg(v) = 2|E|. The proof is a one-liner: each edge contributes exactly 1 to the degree of each of its two endpoints, so summing over all vertices counts each edge exactly twice. This lemma has an immediate corollary: the number of odd-degree vertices in any graph must be even.
Graphs come in several important variants. A *simple graph* has no loops (edges from a vertex to itself) and no multiple edges between the same pair of vertices. A *multigraph* allows multiple edges. A *directed graph* (or digraph) has edges with direction — each edge goes from one vertex *to* another, not just *between* them. The choice of which variant to use depends on what you are modeling: flight routes between cities are naturally a directed graph (routes may be one-way), while friendship networks are typically undirected.
Because you already know set theory, you can use that framework fluently here. The vertex set V and edge set E are just sets; their cardinalities |V| and |E| are the number of vertices and edges. An edge between vertices u and v is an unordered pair {u, v} in the undirected case, or an ordered pair (u, v) in the directed case. This set-theoretic foundation is what lets graph theory scale up to rigorous proofs — you start from definitions and derive everything from there.