Graphs: vertices and edges
A graph is a set of points connected by lines. This simple idea models road maps, social networks, the internet, and molecules.
Definitions
A graph \(G = (V, E)\) has vertices \(V\) and edges \(E\), each edge joining two vertices. Edges may be directed (one-way streets, Twitter follows) or undirected (friendships). A simple graph has no loops (edges from a vertex to itself) and no repeated edges between the same pair.
Degree
The degree of a vertex is the number of edges touching it. The handshake lemma says the sum of all degrees equals twice the number of edges, since each edge has two ends. Consequently, every graph has an even number of odd-degree vertices: you cannot have a party where an odd number of people each shake an odd number of hands.
\sum_{v} \deg(v) = 2|E|Special graphs
The complete graph \(K_n\) connects every pair of \(n\) vertices and has \(\binom{n}{2}\) edges. A cycle \(C_n\) is a ring; a path \(P_n\) is a line. A bipartite graph splits vertices into two groups with edges only between groups, like job applicants and jobs. \(K_{m,n}\) is the complete bipartite graph.
Representing graphs
An adjacency matrix has a 1 in row \(i\), column \(j\) if vertices \(i\) and \(j\) are joined. An adjacency list records, for each vertex, its neighbours. Lists use less memory for sparse graphs (few edges), which most real networks are; matrices allow instant edge lookups.
Paths and connectivity
A path is a sequence of vertices joined by edges; a cycle returns to its start. A graph is connected if every pair of vertices is joined by a path. Disconnected graphs split into connected components, such as separate friend groups in a social network.
Isomorphism
Two graphs are isomorphic if one can be relabelled to become the other: same structure, different names. Checking invariants like the number of vertices, edges, and degree sequences can quickly show two graphs are not isomorphic, though matching invariants do not prove they are.
Worked example
A graph has 6 vertices with degrees 3, 3, 2, 2, 1, 1. The degree sum is 12, so it has 6 edges. Could a graph have degrees 3, 3, 3, 2, 2? The sum is 13, odd, so no such graph exists. The handshake lemma catches impossible specifications instantly.
Applications
Social networks are graphs of people and friendships; the web is a directed graph of pages and links; transport maps are graphs of stations and routes. Google's original PageRank algorithm ranked web pages by analysing this link graph.
Key takeaways
Graphs are vertices joined by edges, directed or undirected. Degrees sum to twice the number of edges. Special graphs include complete, cycle, path, and bipartite graphs. Store graphs as adjacency matrices or lists. Connectivity, components, and isomorphism describe a graph's structure.
Flashcard
A graph
Check your understanding
A graph has degrees 4, 3, 3, 2. How many edges does it have?