What Is a Graph?
A (simple) graph consists of a finite set of vertices together with a set of edges, each edge an unordered pair of distinct vertices. and are adjacent (or neighbors) when . The order of is and its size is .
A graph records only which pairs are connected, not where the vertices sit on the page or in what order you listed them: two very different-looking drawings can be the same graph, an idea made precise in the next topic (Isomorphism and Subgraphs). Writing an edge as the unordered pair rather than the ordered pair builds in that a friendship or a road goes both ways; directed graphs, where , wait until Topic 10. Requiring rules out loops, and simple additionally rules out a repeated edge between the same two vertices, so at most one edge joins any pair. Strip away everything from a map or a circuit diagram except which pairs are joined, and what is left is a graph.
Let have vertex set and edge set . Its order is and its size is . Vertices and are not adjacent, since no edge joins them, while and are, since .
Six teams play a round robin: every pair of teams plays exactly one game. Model this with one vertex per team and an edge per game; every pair of the vertices is joined, so counting edges means counting pairs of teams: games in all. (This all-pairs-joined graph is named in the catalog later in this topic.)
A graph can have vertices and no edges at all: take and . Its order is and its size is — a perfectly good graph, and the extreme opposite of the round robin above, where every pair was joined.
Listing and as two different edges inflates the edge count, since an edge is an unordered pair: is a single edge. In above, , not — double-listing every edge in both orders is the single most common miscount in this course.
Eight teams play a round robin, every pair exactly once. How many games are played?
Show the answerHide the answer
Model it as one vertex per team with an edge per game; every pair of the vertices is joined, so the count is games.
Degree and the Handshake Lemma
The degree of vertex , written , is the number of edges incident to (equivalently, the number of neighbors of ). The handshake lemma:
Each edge has exactly two endpoints, so it adds exactly to and to : a single edge contributes to the total of all degrees, never . Summing degrees is therefore the same as counting (edge, endpoint) pairs, and there are two such pairs per edge, which is the whole proof (spelled out in Why It Works). The lemma is the reason the sum of all degrees is always even, and it is the single most useful counting fact in the subject: a quick parity check rules out whole families of degree sequences before any drawing is attempted. It also makes computable from degrees alone, without ever listing the edges.
In from the last section, , , , , . Summing gives , and indeed : the handshake lemma checks out.
Can people at a party each shake hands with exactly others? If so, the degree sum would be . But is odd, and the handshake lemma forces the degree sum to equal , always even. No such handshaking pattern exists, for any graph, regardless of how the people are arranged.
In a graph of order , no vertex can have degree above (there are only other vertices to be adjacent to); a vertex of degree is isolated, and one of degree is universal. In (order ), the maximum possible degree is ; vertex , with degree , is adjacent to all but one other vertex — it misses only vertex .
Writing undercounts by a factor of : summing the degrees of gives , not . Each edge is counted once at each of its two endpoints, so the degree sum is always , never itself — divide by to recover the edge count.
A graph has edges and degree sequence . Find .
Show the answerHide the answer
By the handshake lemma the degrees sum to . The five known degrees sum to , so .
Degree Sequences
The degree sequence of lists for every vertex, usually sorted . A sequence is graphical if some simple graph has it as its degree sequence. Havel-Hakimi: with is graphical if and only if, after deleting and subtracting from each of the next largest terms, the resulting sequence of length is graphical (the empty sequence is graphical by convention).
The test turns an existence question into an algorithm: repeatedly take the largest remaining degree , connect that vertex to the vertices with the next-largest degrees to use it up, and recurse on the smaller sequence. If this process ever needs a negative degree, the sequence cannot be realized; if it reaches all zeros, reversing the construction builds an explicit graph. The one subtlety the proof must address is why it is always safe to connect the top-degree vertex specifically to the next-highest vertices rather than to any of them; Why It Works shows that if a valid graph exists at all, one exists with that choice too. Degree sequences compress a graph into a single list, and this theorem says exactly which lists are achievable — not every non-increasing list of non-negative integers with an even sum is one.
Is graphical? Its sum is , which is odd. By the handshake lemma the degree sum of any graph is , always even, so no graph has degree sequence — there is no need to even run Havel-Hakimi once the sum fails to be even.
The sum is even, so try Havel-Hakimi. Take the largest degree, (call its vertex ), and connect it to the vertices with the next-largest degrees, (each degree ), reducing them by : the sequence becomes for , i.e. sorted on . Repeat: connect (degree ) to and the next vertex, say , giving on ... following the construction through to the end gives the edges , whose degrees are exactly for . The sequence is graphical.
The sum is , even, so the handshake lemma does not rule it out. Running Havel-Hakimi on terms reaches an all-zero sequence without ever going negative, so it is graphical; carrying out the construction gives the edges on vertices , with degrees exactly as required.
An even sum is necessary but not sufficient. sums to , even, yet Havel-Hakimi fails: deleting the first and subtracting from the next terms gives , and deleting that and subtracting from the next terms gives — a negative degree. No graph has degree sequence , despite the even sum.
Is the degree sequence graphical? If so, build a graph with it.
Show the answerHide the answer
The sum is even. Havel-Hakimi: connect the degree- vertex to all others, using up and reducing the rest to ; then connect the remaining degree- vertex to the next, , reaching all zeros. The edges give degrees for : the sequence is .
A Catalog of Special Graphs
(complete graph): every pair of its vertices is adjacent; and every vertex has degree . (cycle, ): vertices in a ring, each adjacent to and ; and is -regular. (path): vertices in a line; , two endpoints have degree and the rest degree . (complete bipartite): parts of size and with every cross pair adjacent and no edge inside a part; . A graph is -regular if every vertex has degree ; so is -regular and is -regular.
These are the graphs every later topic measures itself against: a Hamiltonian cycle (Topic 6) is literally a copy of sitting inside a bigger graph, a tree (Topic 4) is what is left of a connected graph once every cycle is broken, and is the extreme case of a bipartite graph (Topic 7), with every allowed edge present. Regularity is a symmetry condition: a -regular graph looks the same, degree-wise, from every vertex, and it already tells you by the handshake lemma, before a single edge is drawn. Naming these families turns a drawing into a sentence: saying a network is states everything about its edges at once. The Petersen graph below is the standard example of a graph that is regular without being anywhere close to complete.
For : and every one of the vertices has degree . Check with the handshake lemma: .
A firm has managers and engineers; every manager must hold a one-on-one meeting with every engineer. Model this as , with the managers and engineers as the two parts. The number of meetings is ; each manager attends meetings (degree ) and each engineer attends (degree ). Check: .
The Petersen graph has vertices and is -regular. Counting edges directly from its usual drawing (an outer -cycle, an inner -vertex star, and spokes joining them) gives edges. Counting instead from regularity, by the handshake lemma, gives . Both methods agree.
is not the same as a complete graph on vertices: has edges, one for every pair, including pairs within a side. has only the cross edges and none within a part — mixing the two formulas is the most common error with bipartite graphs.
Find and the degree sequence of .
Show the answerHide the answer
A path on vertices has edges; its two endpoints have degree and the other vertices have degree , so the degree sequence is . Check: .
Adjacency Matrices
For with , the adjacency matrix is the matrix with if and otherwise (so for a simple graph). is symmetric, its -th row sum is , and counts the walks of length from to .
Encoding a graph as a matrix turns combinatorial questions into linear algebra: row sums recover degrees instantly, and matrix powers count walks because builds every length- walk by extending a length- walk one more step, exactly as the proof in Why It Works spells out. The diagonal of is especially useful: , since a closed walk of length from is just out-and-back along one edge. Symmetry reflects that the graph is undirected, ; Topic 10 drops this when the edges point one way. A matrix also mechanizes the whole theory: a computer stores and manipulates instantly, which is how every algorithm later in this course, from shortest paths to coloring, actually runs.
Let have vertices and edges (a -cycle with one diagonal). Its adjacency matrix, in the order , is
Row sums are , matching , , , read directly off the edge list.
Squaring the matrix above gives : there is exactly one walk of length from to , namely (vertex and are already adjacent directly, but that is a walk of length , not ). More strikingly, : vertices and are not adjacent at all, yet there are two length- walks between them, and , one through each of their two common neighbors.
How many triangles does sit inside? Computing and taking its trace gives . Each triangle contributes to this trace (a closed walk can start at any of its vertices and go around in either of directions), so the number of triangles is . Checking directly: is a triangle (edges all present) and so is (edges all present); no other 3-vertex subset has all three edges, so there are exactly triangles, confirming the matrix count.
The diagonal of is for a simple graph, but the diagonal of is usually NOT : in , equal to , since counts closed walks for each of the neighbors . Squaring a matrix with a zero diagonal does not keep the diagonal zero.
In above, how many walks of length are there from vertex to vertex ?
Show the answerHide the answer
A length- walk from to passes through a common neighbor of both. The neighbors of are and the neighbors of are ; their only common neighbor is , giving the single walk . So .
Why It Works
Form the set of (edge, endpoint) pairs . Count it two ways. Grouping by vertex: each appears in this set once for every edge incident to it, so the count is . Grouping by edge: each edge has exactly two endpoints, and , so it contributes exactly pairs, and the count is . The two counts of the same set must agree, so . Corollary: the number of odd-degree vertices is even. Split the sum into vertices of even and odd degree; the even-degree vertices contribute an even total, so the odd-degree vertices must also contribute an even total (an even sum minus an even sum is even). A sum of odd numbers is even only when there is an even count of them, so the number of odd-degree vertices is even.
One direction is immediate: if the reduced sequence is realized by a graph on , add a new vertex joined to exactly (the vertices whose degrees were reduced); this restores their original degrees and gives degree , realizing the original sequence. The other direction needs an exchange argument. Suppose , sorted non-increasingly, is realized by some graph on . If already happens to be adjacent to , deleting realizes the reduced sequence directly. If not, then since but misses some with , must instead be adjacent to some with (to reach degree at all). Since (the sequence is sorted) and is adjacent to but not , while , there must be some vertex adjacent to but not to (otherwise the neighborhood of would contain that of , forcing once the edge to is counted, a contradiction). Swapping edges and for and keeps every degree the same while making adjacent to one more of its intended targets; repeating this swap finitely many times makes adjacent to exactly , after which deleting realizes the reduced sequence.
Induction on . Base case : a walk of length from to is exactly an edge between them, and is if that edge exists and otherwise, so the claim holds. Inductive step: assume counts walks of length from to for every . A walk of length from to is a step from to some neighbor , followed by a walk of length from to ; the step exists exactly when . So the number of length- walks from to is , which is exactly the matrix product entry . This completes the induction.