Difficulty: Introductory to Intermediate | Prerequisites: Basic set notation, familiarity with vertices and edges.
Tags: graph theory, complete graph, K_n, degree sequence, handshaking theorem, directed graph, undirected graph, in-degree, out-degree, simple path, vertex-disjoint path, expression tree, postorder traversal, tree traversal, CS 182, Purdue
Graph theory is one of the central pillars of discrete mathematics and crops up everywhere in computer science, from network routing to social-network analysis to compiler design. This set of notes covers the basics you need cold for an exam: what makes a graph complete, how degree sequences work, the Handshaking Theorem, directed versus undirected graphs, simple and vertex-disjoint paths, and expression-tree traversals. If you are comfortable with sets and can sketch a graph on paper, you are ready for this material.
A complete graph K_n connects every pair of its n vertices. The Handshaking Theorem says the sum of all vertex degrees equals twice the edge count, which forces that sum to be even. Postorder traversal of an expression tree visits left subtree, then right subtree, then the root, producing postfix (reverse Polish) notation.
Complete graph (K_n)
A simple graph on n vertices in which every distinct pair of vertices is joined by exactly one edge. K_n has n(n − 1)/2 edges. In simple terms, every vertex is directly connected to every other vertex, no exceptions.
Degree of a vertex
The number of edges incident to that vertex. In an undirected graph, each edge contributes 1 to the degree of each of its endpoints. Think of it as the number of connections a single vertex has.
Degree sequence
The list of vertex degrees of a graph, typically written in non-increasing order. Not every sequence of non-negative integers is realisable as a degree sequence. In simple terms, it is the "fingerprint" of a graph's connectivity pattern.
Handshaking Theorem (degree-sum formula)
For any undirected graph, the sum of all vertex degrees equals twice the number of edges: Σ deg(v) = 2|E|. A direct consequence is that this sum is always even. Think of it as: every edge is a handshake, and each handshake is counted once by each participant.
Directed graph (digraph)
A graph in which every edge has an orientation, drawn as an arrow from a tail vertex to a head vertex. In simple terms, the connections have a direction, like one-way streets.
In-degree / out-degree
In a directed graph, the in-degree of a vertex is the number of edges pointing into it; the out-degree is the number pointing out. The sum of all in-degrees equals the total number of edges, and likewise for out-degrees.
Simple path
A path in a graph that does not repeat any vertex (and therefore does not repeat any edge). Its length is measured by the number of edges it uses. Think of it as walking through the graph without ever revisiting a junction.
Vertex-disjoint paths
Two paths between the same start and end vertices that share no internal vertices. They may share only their first and last vertices.
Expression tree
A binary tree that represents an arithmetic (or logical) expression. Leaves hold operands; internal nodes hold operators. The structure encodes both the operations and their precedence without needing parentheses.
Postorder traversal
A tree-traversal order that visits the left subtree, then the right subtree, then the root. Applied to an expression tree, it produces postfix notation (reverse Polish notation).
K_n is the unique simple graph (no loops, no multi-edges) where every pair of distinct vertices is adjacent.
Edge count: n(n − 1)/2. So K_4 has 6 edges, K_5 has 10, and so on.
To check whether a drawn graph is complete, verify that no edge is missing between any pair of vertices. Even a single missing edge disqualifies it.
Core result: Σ deg(v) = 2|E|.
Because the right-hand side is always even, the sum of degrees in any undirected graph is even. If someone gives you a list of degrees that sums to an odd number, no such graph exists.
Example: a graph with 14 edges has a degree sum of 28, not 30.
When asked whether a sequence of numbers can be the degree sequence of a simple graph on n vertices, check these quick filters:
The sum must be even (Handshaking Theorem).
No degree can exceed n − 1 (a vertex cannot connect to itself in a simple graph).
If a vertex has degree n − 1, it is adjacent to every other vertex, so every other vertex must have degree at least 1.
If two vertices both have degree n − 1, every other vertex must have degree at least 2.
For a rigorous check, apply the Erdős–Gallai theorem or the Hakimi algorithm, but the filters above catch most exam questions.
Example (6 vertices):
5, 3, 2, 2, 2, 0 is invalid. Degree 5 means adjacent to all five others, but one vertex has degree 0, a contradiction.
3, 3, 3, 3, 2, 0 is valid and can be constructed.
3, 3, 3, 2, 2, 2 sums to 15 (odd), so it is invalid by the Handshaking Theorem.
5, 5, 3, 2, 2, 1 is invalid. Two vertices of degree 5 force every other vertex to have degree at least 2, but one has degree 1.
In a digraph, each edge contributes exactly 1 to the in-degree of its head and 1 to the out-degree of its tail.
Sum of all in-degrees = sum of all out-degrees = total number of edges.
Recognising a directed graph on sight: the edges are drawn with arrowheads.
A simple path cannot use more edges than the graph contains, because it never repeats an edge (and, being simple, never repeats a vertex either).
If a graph has 6 edges, no simple path can have length 8.
In a connected graph, a simple path exists between every pair of vertices.
Two vertex-disjoint paths between the same endpoints share only those endpoints. In a cycle graph, for any pair of vertices, the clockwise path and the counterclockwise path are vertex-disjoint.
An expression tree is a binary tree where leaves are operands and internal nodes are operators.
Traversal orders:
Preorder (root, left, right) produces prefix notation.
Inorder (left, root, right) produces infix notation (the familiar one, but may need parentheses).
Postorder (left, right, root) produces postfix notation.
To generate the postorder sequence, recurse into the left subtree first, then the right subtree, then write down the current node.
Example: for an expression tree representing ((4 + 3) 7) - ((5 / 3) + 4) + 6, the postorder output is 4 3 7 + 5 3 4 + / - 6 +.
Result | Formula |
|---|---|
Edges in K_n | n(n − 1) / 2 |
Handshaking Theorem | Σ deg(v) = 2 |E| |
In-degree sum (digraph) | Σ in-deg(v) = |E| |
Out-degree sum (digraph) | Σ out-deg(v) = |E| |
The Handshaking Theorem is not just exam trivia. Network engineers use it to verify link counts in physical topologies: if you sum up the port connections at every switch and router, you should get exactly twice the number of cables. If the total is odd, something has been miscounted, and there is a cabling error somewhere.
Expression trees underpin how compilers parse and evaluate arithmetic expressions. The postorder form (postfix) is directly executable on a stack machine, which is why languages like Forth and PostScript use it natively.
Students often assume any non-increasing list of non-negative integers can be a degree sequence. It cannot; the Handshaking Theorem and adjacency constraints impose real restrictions.
"The sum of degrees equals the number of edges" is a common misquote. The sum of degrees equals twice the number of edges. Getting this factor of 2 wrong is one of the most frequent exam errors.
Students sometimes confuse "simple path" with "path that does not repeat edges." A simple path does not repeat vertices (which is a stricter condition). A walk that merely avoids repeated edges is called a trail.
In postorder traversal, students often write the root first or mix up left and right subtree order. The root comes last, always.
⚠️ Expect a question that gives you a degree sequence and asks whether it is valid. Run the Handshaking parity check first, then check max-degree constraints.
⚠️ Directed-graph questions often ask for the sum of in-degrees. Remember: it equals the number of edges, not twice the number.
⚠️ Expression-tree traversal is a standard exam question. Practise generating preorder, inorder, and postorder from a given tree until it is automatic.
⚠️ "Simple path of length k" means exactly k edges. If the graph has fewer than k edges, the answer is immediately impossible.
True or false: K_6 has 16 edges.
True or false: the sum of degrees in any undirected graph is always even.
Fill in the blank: in a directed graph, the sum of all in-degrees equals ______.
True or false: a simple path may revisit a vertex.
Fill in the blank: postorder traversal visits the subtrees in the order ______, ______, then the root.
Answers: (1) False, K_6 has 6·5/2 = 15 edges. (2) True. (3) The number of edges. (4) False. (5) Left, right.
Q: A simple graph has 6 vertices. The proposed degree sequence is 5, 5, 3, 2, 2, 1. Is this realisable? Explain why or why not.
A: No. Two vertices of degree 5 means each is adjacent to all five others, so every other vertex must have degree at least 2. But the sequence contains a vertex of degree 1, which contradicts this requirement.
Q: An undirected graph G has 14 edges. What is the sum of all vertex degrees in G?
A: By the Handshaking Theorem, the sum is 2 × 14 = 28.
Q: A directed graph H has 7 edges. What is the sum of all in-degrees in H?
A: The sum of in-degrees in any digraph equals the number of edges, so 7.
Q: Why can a graph with 6 edges never contain a simple path of length 8?
A: A simple path does not repeat edges. With only 6 edges in the entire graph, no path (simple or otherwise) can traverse 8 distinct edges.
Q: Given an expression tree, what traversal order produces postfix notation?
A: Postorder traversal (left subtree, right subtree, root).
Degree sequences connect directly to the Erdős–Gallai theorem and the Hakimi algorithm, both of which appear in more advanced discrete-maths courses.
Graph connectivity ties into network flow and Menger's theorem, where vertex-disjoint paths play a central role.
Expression-tree traversals reappear in compiler construction (syntax trees, intermediate code generation) and in data-structures courses when discussing stack-based evaluation.
complete graph, K_n, clique, degree, valency, degree sequence, graphic sequence, handshaking lemma, degree-sum formula, directed graph, digraph, in-degree, out-degree, simple path, trail, walk, vertex-disjoint, edge-disjoint, Menger's theorem, expression tree, parse tree, abstract syntax tree, preorder, inorder, postorder, prefix notation, infix notation, postfix notation, reverse Polish notation, CS 182, Purdue, foundations of computer science