Key takeaways
- A graph is a set of vertices together with a set of edges, each edge joining two vertices; the drawing is just a picture of that structure.
- The degree of a vertex is the number of edges meeting it.
- The handshake lemma: the degrees add up to twice the number of edges, because every edge has two ends.
- So every graph has an even number of vertices of odd degree, and seven people cannot each shake hands with exactly three others.
- The complete graph Kₙ, with every pair of vertices joined, has n(n − 1)/2 edges.
In graph theory a "graph" is not a plot of y against x. It is a network: a set of points and a set of connections between them. That simple structure can model road maps, computer networks, friendships, timetables and the dependencies between tasks.
Vertices, edges and adjacency
Applied Discrete Structures defines a simple undirected graph as a nonempty set V of vertices together with a set E of edges, each edge being a set of two distinct vertices. An edge {u, v} joins u and v, and u and v are then adjacent.
Example. V = {a, b, c, d, e} and E = {ab, ac, bc, cd, de}. Drawn on paper, a, b and c form a triangle, c is joined to d, and d to e.
The drawing is only a picture. Moving the dots around, or drawing edges as curves, gives the same graph, because the graph is the sets V and E. Whether two different-looking drawings are the same graph is the subject of graph isomorphism.
Variations you will meet
| Kind | What changes | Example use |
|---|---|---|
| Simple graph | No loops, at most one edge per pair | Friendships |
| Multigraph | Several edges may join the same pair | Bridges between two islands |
| Directed graph (digraph) | Edges have a direction, from u to v | One-way streets, web links |
| Weighted graph | Each edge carries a number | Road distances, network costs |
Applied Discrete Structures defines multigraphs explicitly, and directed graphs come first in its treatment; Levin's Discrete Mathematics: An Open Introduction starts with simple graphs. Most first results are stated for simple undirected graphs, and this guide sticks to them unless it says otherwise.
Degree
The degree of a vertex is the number of edges that meet it. In the example: deg(a) = 2, deg(b) = 2, deg(c) = 3, deg(d) = 2, deg(e) = 1. A vertex of degree 0 is isolated; a vertex of degree 1 is sometimes called a leaf, a term that matters for trees.
The handshake lemma
Add up the degrees in the example: 2 + 2 + 3 + 2 + 1 = 10. The graph has 5 edges. That is no coincidence.
Handshake lemma. In any graph, the sum of the degrees of all the vertices is twice the number of edges.
Proof. Each edge has two ends, and it adds 1 to the degree of each. So when you add all the degrees, every edge is counted exactly twice. ∎
Levin's book states it in the same words, and MathWorld explains the name: think of vertices as people and edges as handshakes. If everyone reports how many hands they shook, the total is twice the number of handshakes, because each handshake involves two people.
Consequence: odd-degree vertices come in pairs. The degree sum is even. The even degrees contribute an even amount, so the odd degrees must also add to an even number, which means there must be an even number of them.
Application. Can 7 people at a party each shake hands with exactly 3 others? That would give a degree sum of 7 × 3 = 21, which is odd. So it is impossible, and you can say so without trying a single arrangement.
Paths, cycles and connectivity
- A walk is a sequence of vertices in which each consecutive pair is joined by an edge.
- A path is a walk that never repeats a vertex.
- A cycle is a path that returns to its start, such as a → b → c → a.
- A graph is connected if there is a path between every pair of vertices. A disconnected graph splits into components, its connected pieces.
The example graph is connected and has exactly one cycle, the triangle abc.
Definitions here vary slightly between books, especially about whether a walk may repeat edges, so check which version your course uses.
Special graphs
| Graph | Description | Edges |
|---|---|---|
| Complete graph Kₙ | Every pair of n vertices joined | n(n − 1)/2 |
| Cycle Cₙ | n vertices in a ring | n |
| Path Pₙ | n vertices in a line | n − 1 |
| Complete bipartite Kₘ,ₙ | Two groups, every cross pair joined | mn |
The edge count of Kₙ is C(n, 2), one edge per pair, and the handshake lemma agrees: n vertices of degree n − 1 give a degree sum of n(n − 1), so n(n − 1)/2 edges. K₅ has 10 edges. Graphs whose vertices split into two groups with edges only between them are covered in bipartite graphs.
What the rest of graph theory asks
Much of the graph theory in a first course comes back to a handful of questions about these objects:
- Can you travel along every edge exactly once? That is an Euler path, and the degrees decide it.
- Can you visit every vertex exactly once? That is a Hamiltonian path, and no simple test exists.
- How few colours can label the vertices so that neighbours differ? That is graph colouring.
- How do you store a graph in a computer? See adjacency matrices and lists.
OpenStax's Contemporary Mathematics opens its graph theory chapter with the same basic vocabulary, and its exercises are a good source of small graphs to practise on.
Degree-sequence exercises
- A graph has degrees 3, 3, 2, 2, 2. How many edges does it have? (12/2 = 6.)
- Draw a simple graph with degrees 3, 2, 2, 2, 1. (One answer: join v₁ to v₂, v₃ and v₄, join v₂ to v₃, and join v₄ to v₅.)
- Is there a simple graph with degrees 3, 3, 3, 1? (The sum is even, so the lemma allows it, but no: with four vertices, each degree-3 vertex is joined to all three others, so the fourth vertex would have degree 3. The lemma is necessary, not sufficient.)
Graph theory is the last unit of Discrete Math: Study & Quiz. Find it among our education apps, and the rest of the graph guides in the discrete math hub.
Good to know
Frequently asked questions
What is a graph in discrete math?
What is the handshake lemma?
How many edges does a complete graph have?
What is the difference between a walk, a path and a cycle?
Sources
- Graph Theory: Definitions (Discrete Mathematics: An Open Introduction, 3rd edition, Oscar Levin) (opens in a new tab)Open Math Books — accessed
- Graphs: General Introduction (Applied Discrete Structures) (opens in a new tab)discretemath.org — accessed
- Handshaking Lemma (opens in a new tab)Wolfram MathWorld — accessed
- 12.1 Graph Basics (Contemporary Mathematics) (opens in a new tab)OpenStax — accessed
About the author
Reign Creative LLC — The independent app studio that builds the apps covered on this site and publishes every article here. On Google Play it publishes as Reign Collective Apps.
We use AI tools to help research, draft and edit our articles. Each article lists the sources its factual claims rely on, and details about our apps come from their live Google Play listings. No article on this site has been reviewed by an independent expert unless the reviewer is named on it.
No person at Reign Creative LLC has read this article in full. It was published after automated checks and an AI editorial review, which are described in our editorial policy and are not the same as a person reading every sentence.
Spotted an error? Tell us — how corrections are handled is set out in our editorial policy.