A graph is a set of vertices together with a set of edges joining pairs of them -- nothing more, nothing less. This whole course is built on that one object, so before Chapter 1 starts formalizing it with real notation, it's worth confirming the two ideas that sit right underneath it: how many edges touch a given vertex, and the one exact relationship that has to hold between all those counts and the graph's total edge count.
Picture every edge as a handshake between the two vertices it connects. Each vertex's degree is how many hands it shook. Now add up everybody's handshake count across the whole room. Every single handshake gets counted twice in that total -- once from each side of it -- so the grand total always comes out even, and it's always exactly double the number of handshakes that actually happened. That's the whole theorem. It also means a room where an odd number of people shook an odd number of hands is a room that never happened -- someone's count is wrong, before you even see who supposedly shook what.
A vertex's degree is the number of edges touching it; a self-loop at a vertex counts twice toward that vertex's own degree, since both of its ends attach there. The handshaking theorem is the exact relationship this forces on those degree numbers: their sum, across an entire graph, is locked to exactly twice the edge count, because every single edge has two ends, and each end adds one to the degree of whichever vertex it lands on. Counting "one end at a time" across every edge counts each edge exactly twice, which is the whole proof in one sentence.
The theorem's most useful corollary is a parity fact, not a counting one: the number of odd-degree vertices in any graph is always even. That's not a separate coincidence -- an even total (twice the edge count) can only be built by adding an even number of odd numbers together, since every even-degree vertex already contributes an even amount and can't be what tips the sum's parity. This is the fact that catches a broken graph before anyone even draws it: a degree list with an odd number of odd entries cannot belong to any real graph, full stop.
Quick review
Practice from earlier coursework, pulled in for this topic.
From Discrete Mathematics I — Logic, Proof, and Structure
In an adjacency matrix A for an undirected simple graph, how is deg(v) computed?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Vertex count is unrelated to any one vertex's own degree.
The diagonal entry, for a simple graph with no loops, is always 0 -- it says nothing about degree.
Summing the whole matrix gives twice the total edge count across all vertices, not one vertex's degree.
Why
Row v's entries mark exactly which vertices v is adjacent to, so their sum is v's degree.
From Discrete Mathematics I — Logic, Proof, and Structure
A vertex v has one loop and three ordinary edges to distinct other vertices. What is deg(v)?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
The loop contributes 2, and the three ordinary edges each contribute 1: 2+1+1+1=5.
Correct answer
Also accepted:
Why
Quick review
Practice from earlier coursework, pulled in for this topic.
From Discrete Mathematics I — Logic, Proof, and Structure
A graph has 8 edges. What is the sum of all its vertex degrees?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
The handshaking theorem gives sum of deg(v) = 2|E| = 2(8) = 16.
Correct answer
Also accepted:
Why
From Discrete Mathematics I — Logic, Proof, and Structure
A graph has vertex degrees summing to 24. How many edges does it have?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
Solving 2|E| = 24 gives |E| = 12.
Correct answer
Also accepted:
Why
Theorem
The Handshaking Theorem
also known as: the degree-sum formula
Recalled from Discrete Mathematics I — Logic, Proof, and Structure · The handshaking theorem — first taught there.
For any graph G with vertex set V and edge set E, \sum_{v \in V} \deg(v) = 2|E|. In particular, the sum of all vertex degrees in any graph is always even, and so the number of vertices with odd degree is always even.
Each edge e = \{u, v\} of G has exactly two endpoints, u and v (a loop at v is the case u = v, still contributing two to that one vertex's degree count, which is exactly why a loop is defined to add 2 to \deg(v) rather than 1). Build the sum \sum_{v\in V}\deg(v) by counting, for every edge, how many times that edge gets counted across the whole sum.
Fix one edge e=\{u,v\}. It is counted once when computing \deg(u) (since e is incident to u) and once more when computing \deg(v) (since e is also incident to v), and it is never counted in any other vertex's degree, since e touches no vertex besides u and v. So every edge contributes exactly 2 to the total \sum_{v\in V}\deg(v), and there are |E| edges, giving \sum_{v \in V} \deg(v) = \sum_{e \in E} 2 = 2|E|.
The odd-degree count is even. Split V into V_{\text{even}} (even degree) and V_{\text{odd}} (odd degree). Then \sum_{v \in V_{\text{even}}} \deg(v) + \sum_{v \in V_{\text{odd}}} \deg(v) = 2|E|, an even number. The first sum is a sum of even numbers, so it's even. Subtracting an even number from an even number leaves an even number, so \sum_{v \in V_{\text{odd}}} \deg(v) is even too. A sum of odd numbers is even only when there is an even count of them (an odd count of odd numbers always sums to something odd), so |V_{\text{odd}}| itself must be even.
Sanity check: a triangle (3 vertices, each of degree 2) has degree sum 2+2+2=6, and 2|E| = 2(3) = 6 -- matches, and 0 vertices have odd degree, which is indeed even.
Read degrees off the matrix, then check the theorem
Click a vertex to see which row is its own. Count how many 1's sit in each vertex's row (its degree), add all five, and confirm the total is twice the number of edges.
Loading interactive…
Recipe Check a degree list and find the edge count Use when: you're given a list of vertex degrees, with no picture of the graph, and asked whether it's valid, how many edges it has, or both Goal: either a confirmed impossible list, or a valid one paired with its exact edge count
Quick recipe
-
1
Sum all the numbers in the given degree list. That total will need to satisfy one exact requirement in the next step, whether or not you've ever seen the actual graph.
Example
For the degree list 3, 2, 2, 2, 3: 3+2+2+2+3=12.
Why: the handshaking theorem ties this sum directly to the edge count, so nothing else about the graph's layout matters yet.
-
2
A valid degree list's sum must come out even, since the handshaking theorem says the sum always equals twice the edge count. An odd sum means no real graph has this degree list.
Example
12 is even, so 3, 2, 2, 2, 3 passes this check.
- the sum is odd — the list is impossible, stop here
- the sum is even — the list survives this check, continue to Step 3
⚡ Shortcut
Skip adding the whole list first: count how many degrees are odd. If that count is odd, the list fails immediately, with no addition needed at all. For 3, 3, 3, 2: three entries (3, 3, 3) are odd, an odd count, so this list is impossible on sight, without ever computing 3+3+3+2=11.
Why: an even total can only be built from an even number of odd addends, since every even-degree entry can never flip the sum's parity.
-
3
Divide the sum from Step 1 by 2 to get the number of edges. The handshaking theorem guarantees this comes out to a whole number whenever Step 2 passed.
Example
12 \div 2 = 6, so a graph with degree list 3,2,2,2,3 has exactly 6 edges.
Why: the theorem states the degree sum equals exactly twice the edge count, so this division is the only step left once the sum is confirmed valid.
Common mistakes
- Declaring a list "definitely realizable" just because its sum is even -- an even sum is necessary, not sufficient, for a real graph to exist.
- Forgetting the odd-degree-count shortcut only ever proves impossibility, never confirms that a graph actually exists.
- Dividing the degree sum by the vertex count instead of by 2.
- Skipping the parity check and jumping straight to |E| = (\text{sum})/2, missing an impossible list entirely.
Worked example
Reading a degree straight off a drawing
-
1
A graph has vertices A, B, C, D, E and edges AB, AC, AE, BC, CD, DE. What is the degree of C?
-
2
List every edge that has C as one of its two endpoints: AC, BC, CD. That's three edges touching C, and no edge is listed twice.
-
3
Count that list directly -- no need to redraw the graph or consult anything else.
-
4\boxed{\text{degree of } C = 3}
Loading interactive…
Worked example
Finding the edge count from a degree list, without seeing the graph
-
1
A graph's five vertices have degrees 3, 2, 2, 2, 3. How many edges does the graph have? This runs Steps 1 and 3 of the recipe above on exactly this list.
-
2
The handshaking theorem needs only the degree numbers, never the graph's actual layout or which vertices connect to which.
-
3
Add the degrees: 3+2+2+2+3=12. That total is twice the edge count, so solve 12 = 2|E| for |E|.
-
4\boxed{|E| = 6}
Loading interactive…
Worked example
Catching an impossible degree list
-
1
Someone claims a graph has four vertices with degrees 3, 3, 2, 4. Is that possible? This is Step 2 of the recipe above, the parity check, run on a new list.
-
2
Check the odd-degree count first, since the handshaking theorem's corollary is the fastest test available: exactly two of these four numbers, 3 and 3, are odd.
-
3
Two is even, so the parity test doesn't rule this out by itself -- confirm with the full sum: 3+3+2+4=12, which is even, consistent with 2|E| for some whole number of edges |E|=6.
-
4\boxed{\text{Possible as far as the theorem can tell} - \text{sum is even, }|E|=6}
Passing this check doesn't prove a graph with this exact degree list exists, only that the one necessary condition the theorem gives isn't violated. Compare that to a claimed list like 3,3,3,2: three odd entries, an odd count of them, which the theorem rules out immediately, no further check needed.
Where this goes next
Network design
An engineer sanity-checking a proposed network topology's link count against its routers' stated connection counts is applying the handshaking theorem directly. If the degree sum the equipment inventory reports comes out odd, or the count of routers with an odd number of connections is odd, something in that inventory is wrong before a single cable gets run -- no real network, and no real graph, can violate either fact.
Check your understanding (counts toward your progress)
A graph is described as: vertex A connects to everyone else in a 6-vertex graph, and no other edges exist. What is A's degree?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
A doesn't connect to itself -- only to the other 5 vertices.
Every one of the 5 other vertices gets its own edge to A, not a single shared one.
Why
A connects to each of the 5 other vertices once, and no self-loop is mentioned, so its degree is 5.
Count how many other vertices exist besides A itself, since A can't have an edge to itself.
In a friendship graph, Priya is friends with 4 people, and one of those friendships is mutual with someone who is also friends with 2 other people not counting Priya. What is Priya's degree in the friendship graph?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
Degree only counts Priya's own direct edges -- her 4 friendships -- regardless of how many friends each of her friends separately has.
Correct answer
Also accepted:
Why
Degree only counts edges touching Priya herself -- check whether the extra fact about her friend's other friendships actually adds an edge at Priya.
A student lists the edges touching vertex V as VA, VB, VV (a self-loop) and reports \deg(V) = 3. What's wrong?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
A self-loop's contribution was undercounted.
A self-loop isn't ignored -- both of its ends attach to the same vertex, and both ends count.
Self-loops are a legitimate (if less common) feature of a graph, not a forbidden structure.
Why
Both ends of a self-loop land on the same vertex, so it contributes 2 to that vertex's degree: VA, VB, and the loop's two ends give 1+1+2=4.
Work out how many times a self-loop's two ends attach to the same vertex, then add that separately from the two ordinary edges.
A graph's vertices all have the same degree k (a regular graph). If k is odd, what must be true of the number of vertices n?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
An odd vertex count paired with every vertex at odd degree would make the total degree sum odd, which the handshaking theorem forbids.
The handshaking theorem constrains this combination directly -- it isn't unrestricted.
Degree and vertex count are independent quantities in general.
Why
The degree sum is nk, and the handshaking theorem requires that sum to be even. With k odd, n must be even to keep the product even.
Write the total degree sum in terms of n and k, then recall what the handshaking theorem requires that total to be.
With k odd, work out what parity n must have to keep the product nk even.
Practice: Reading and reasoning about degree (5 problems · doesn’t affect your progress)
A vertex touches 4 edges, one of which is a self-loop. Is its degree 4 or 5?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
A self-loop contributes 2 to a vertex's degree (both its ends land on the same vertex), so 3 ordinary edges plus one self-loop give 3+2=5.
Work out separately how much an ordinary edge contributes to degree, versus how much a self-loop's two ends contribute.
5
A graph has edges AB, AC, BC, BD. What is the degree of B?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
Three edges touch B: AB, BC, BD.
Correct answer
Also accepted:
Why
A graph has vertices A,B,C,D,E with every pair adjacent (a complete graph). What is the degree of any one vertex?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
Each vertex connects to the 4 other vertices, one edge apiece.
Correct answer
Also accepted:
Why
Count how many other vertices exist in this 5-vertex complete graph, since every pair is adjacent.
A vertex v has the highest degree in its graph. Does this mean v is adjacent to every other vertex?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
Having the highest degree only means no other vertex beats it -- it says nothing about reaching every vertex in the graph, which only a complete graph's vertices actually do.
Think of a specific graph where one vertex beats every other vertex's degree without connecting to literally everyone.
No -- having the highest degree doesn't require being adjacent to everyone, only to more vertices than any other single vertex is
A simple graph (no loops or repeated edges) has 6 vertices. What is the largest possible degree any vertex could have?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
Without loops or repeated edges, a vertex can connect to at most each of the other 5 vertices once.
Correct answer
Also accepted:
Why
Rule out a vertex connecting to itself, and rule out more than one edge to the same other vertex.
Count exactly how many other vertices remain once those two restrictions are applied.
Check your understanding (counts toward your progress)
A graph's vertices have degrees 2, 2, 3, 3, 2. How many edges does the graph have?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
Sum the degrees: 2+2+3+3+2=12, then divide by 2: 12/2=6.
Correct answer
Also accepted:
Why
A graph has 6 vertices, and every vertex has degree 4 (a 4-regular graph). How many edges does it have?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
The degree sum is 6 \times 4 = 24, so the edge count is 24/2 = 12.
Correct answer
Also accepted:
Why
Find the total degree sum across all six vertices before dividing by two.
A graph has exactly 2 vertices of odd degree. What can you conclude?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
The handshaking theorem's corollary says nothing about connectivity.
Edge count isn't constrained to be odd or even by this fact alone.
This is exactly the allowed case -- an even count (here, 2) of odd-degree vertices is completely consistent with the theorem.
Why
The corollary requires the count of odd-degree vertices to be even, and 2 satisfies that -- there's nothing here that rules the graph out.
Recall exactly what the handshaking theorem's corollary restricts -- the count of odd-degree vertices, not anything about connectivity or edges.
Check whether 2 satisfies that even-count requirement before assuming something is wrong.
Which of these two degree lists can be ruled out immediately by the odd-degree-count corollary: (3,3,3,2) or (3,3,2,2)?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Count again -- (3,3,2,2) has two odd entries, 3 and 3, and two is an even count, so this one is NOT ruled out.
Only one of the two lists actually fails the odd-count test.
(3,3,3,2) has three odd entries -- an odd count -- which is exactly the case the corollary rules out.
Why
(3,3,3,2) has three odd entries (3, 3, 3), an odd count, so no graph can have this degree list. (3,3,2,2) has only two odd entries (3, 3), an even count, so it isn't ruled out by this test.
Count how many entries in each list are odd numbers, then check whether that count itself is even or odd.
Practice: The handshaking theorem, from both directions (5 problems · doesn’t affect your progress)
In your own words, explain why the sum of every vertex's degree in a graph must always come out even.
AI grading isn't configured on this deployment.
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
First mistake
Correct answer
Also accepted:
Why
Why
Every edge has exactly two ends, and each end adds 1 to some vertex's degree, so each edge contributes exactly 2 to the grand total -- an even amount, added once per edge, so the whole sum is even.
Think about how many vertices a single edge touches, and how many times that edge gets counted when you add up every vertex's degree.
A graph's degrees are 1, 1, 2, 2, 2. How many edges does it have?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
1+1+2+2+2=8, and 8/2=4 edges.
Correct answer
Also accepted:
Why
A graph has 20 edges. What is the sum of every vertex's degree?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
The handshaking theorem gives exactly 2\times 20 = 40.
Correct answer
Also accepted:
Why
Apply the handshaking theorem's relationship directly: the sum equals twice the edge count.
A degree list has exactly 1 vertex of odd degree, and the rest even. Is this list possible?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
The number of odd-degree vertices must always be even; a count of exactly 1 violates that corollary immediately, no graph can have this list.
Check the parity of the count of odd-degree vertices against what the corollary requires, not the parity of any individual degree.
No -- the odd-degree count (1) is itself odd, which the theorem forbids
A 5-regular graph (every vertex has degree 5) has 8 vertices. How many edges does it have?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
The degree sum is 8\times 5=40, so the edge count is 40/2=20.
Correct answer
Also accepted:
Why
Find the total degree sum across all eight vertices first.
Divide that total by two to reach the edge count.
Practice: Graphs, what actually counts as one (5 problems · doesn’t affect your progress)
A graph is made up of exactly two ingredients. What are they?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
A graph is nothing more than a set of vertices together with a set of edges joining pairs of them -- distance, color, and position on a page are never part of the definition.
Vertices and edges
Two drawings connect the exact same pairs of vertices, but one draws every edge as a gentle curve and the other draws every edge as a straight line. Are they the same graph?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
A graph's identity is just its vertices and which pairs of them are joined -- how an edge happens to be drawn carries no mathematical meaning at all.
Yes -- only which pairs are joined matters, not how the edges are drawn
An edge e joins vertices A and B. Vertex A and edge e itself are said to be...
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
A vertex and an edge that touches it are called incident; 'adjacent' instead describes the relationship between the two vertices themselves.
This question asks about a vertex's relationship to an edge touching it, not the relationship between the two vertices at either end.
Incident
A graph's edges are \{A,B\}, \{B,C\}, \{C,A\}, and vertex D is also declared as part of the graph, even though no edge touches it. How many vertices does this graph have in total?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
A graph's vertex set is whatever it's declared to be; D belongs to it regardless of having zero edges, so the total is A,B,C,D -- four vertices.
Correct answer
Also accepted:
Why
Count every vertex the graph actually declares, not only the ones that happen to appear in the edge list.
A map lists every trail segment between landmarks, but never separately lists the landmarks themselves. Is that edge list alone always enough to reconstruct the graph exactly, including a landmark with no trail touching it at all?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
An edge list only ever mentions vertices that touch at least one edge, so an isolated landmark -- one with no trail at all -- would vanish from it entirely; a graph needs its vertex set stated separately to capture that.
Think about whether a list of connected pairs could ever happen to name a vertex that has no edges at all.
Decide what that gap means for whether the edge list by itself always reconstructs the full vertex set.
No -- an edge list alone can never mention a vertex that touches zero edges