Graphs return in this course's final chapters as objects to be counted — how many labeled graphs exist on n vertices, how many spanning trees a graph has — rather than objects to be classified, so their vocabulary needs to already be automatic.
Degree counts how many roads leave an intersection. Add up every intersection's road count. Every road gets counted from both ends. So the total is always exactly double the road count, no matter the map's shape. A connected map lets you drive from any intersection to any other. A disconnected map is really several separate maps sharing one page. To check which kind a map is, just start driving from one intersection. See how much of the map you can reach. Reach everything, and it's connected. Get stuck with roads still unreached, and each stuck-together cluster is its own separate map.
A graph is a set of vertices and a set of edges connecting pairs of them; a vertex's degree is how many edges touch it. The handshaking theorem, \sum_v \deg(v) = 2|E|, holds because every edge contributes exactly 2 to the total — one to each endpoint — so the sum of all degrees is always even. Connectedness is the property of every vertex being reachable from every other by some path; a graph either has it outright, or it breaks apart into separate pieces called components, each internally connected but disconnected from every other component. Testing connectedness on a small graph is a matter of trying to reach every vertex from any one starting point — if the attempt ever gets stuck, the unreached vertices form at least one more component.
Quick review
Practice from earlier coursework, pulled in for this topic.
From Discrete Mathematics I — Logic, Proof, and Structure
A vertex with degree exactly 1 is called what?
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.
Isolated means degree 0, not 1.
A loop is a kind of edge, not a description of a vertex's degree.
Why
A vertex with exactly one incident edge is called a leaf, or pendant vertex.
From Discrete Mathematics I — Logic, Proof, and Structure
Edges: {A,B}, {A,C}, {A,D}, {B,C}. What is deg(A)?
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 appears in three edges: {A,B}, {A,C}, {A,D}.
Correct answer
Also accepted:
Why
Quick review
Practice from earlier coursework, pulled in for this topic.
From Discrete Mathematics I — Logic, Proof, and Structure
An isolated vertex with no edges at all counts as what?
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.
Components are defined by path-reachability, not proximity -- an isolated vertex reaches nothing else.
Every vertex belongs to exactly one component, even one with no edges.
Why
An isolated vertex has a path to no other vertex, so it forms a component consisting of just itself.
From Discrete Mathematics I — Logic, Proof, and Structure
Vertices A,B,C,D,E,F. Edges: A-B, B-C, D-E. Vertex F has no edges at all. How many components?
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,B,C}, {D,E}, and the isolated vertex {F} give three components in total.
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.
Confirm the handshaking theorem on a small graph
Read off each vertex's degree from the matrix, sum them, and compare to twice the edge count.
Loading interactive…
Worked example
Reading degree and connectedness off a small graph
-
1
A graph has vertices \{A,B,C,D\} and edges AB, BC, CA. What is \deg(D), and how many components does the graph have?
-
2
D touches no edge in the list, so its degree is 0; A, B, C form a connected triangle, disconnected from D.
-
3
Count the components directly: the triangle is one component, and the isolated vertex D is a second.
-
4\boxed{\deg(D)=0, \quad 2 \text{ components}}
Loading interactive…
Worked example
Using the handshaking theorem as a check
-
1
A graph's four vertices have degrees 3, 3, 2, 2. How many edges does it have, without seeing the graph itself?
-
2
The handshaking theorem needs only the degree sum, not the graph's actual layout: 3+3+2+2=10.
-
3
Solve \sum \deg(v) = 2|E| for |E|: divide the degree sum by 2.
-
4\boxed{|E| = 5}
Loading interactive…
Where this goes next
Network design
A network engineer sanity-checking a proposed topology's link count against its routers' stated connection counts is applying the handshaking theorem directly — if the degree sum an equipment list reports is odd, something in the inventory is wrong before a single cable gets run, since no real graph can have an odd degree sum.
Check your understanding (counts toward your progress)
A graph's vertices have degrees 2, 3, 3, 4, 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+3+3+4+2=14) and divide by 2 (handshaking theorem): 14/2=7.
Correct answer
Also accepted:
Why
A graph is claimed to have exactly one vertex of odd degree, all others even. Is this 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
Since the degree sum is always even, the odd-degree vertices must sum to an even total among themselves, which forces their COUNT to be even -- never exactly one.
Recall what the handshaking theorem says about the parity of the sum of all degrees.
If exactly one vertex had odd degree and every other vertex had even degree, think about what that would force the total degree sum's parity to be.
A connected graph with 6 vertices has 5 edges. What is the sum of all 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 the sum directly: 2|E| = 2(5) = 10, regardless of the graph's exact shape.
Correct answer
Also accepted:
Why
Apply the handshaking theorem directly to the edge count -- the graph's exact shape doesn't matter here.
A graph has 3 vertices with no edges among them at all. How many components 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.
Each isolated vertex is its own component -- they aren't connected to each other.
Why
Every isolated vertex is its own component; 3 vertices with no edges means 3 separate components.
Practice: Graphs, degree, and what stays connected (5 problems · doesn’t affect your progress)
A graph is drawn with 5 dots and some lines connecting pairs of them. What are the formal names for the dots and the lines?
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.
'Node' and 'path' aren't the standard pair here -- a path is a specific sequence of edges, not the plain connecting lines themselves.
This swaps the two terms -- the dots are vertices, and the lines connecting them are edges.
'Component' and 'degree' name entirely different graph properties, not the dots and lines themselves.
Why
A graph consists of vertices (the dots) and edges (the lines connecting pairs of them) -- the two basic building blocks every other graph definition builds on.
Dots are vertices, lines are edges
A graph's vertices have degrees 2, 3, 3, 4, 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+3+3+4+2=14) and divide by 2 (handshaking theorem): 14/2=7.
Correct answer
Also accepted:
Why
A graph has 3 vertices with no edges among them at all. How many components 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.
Each isolated vertex is its own component -- they aren't connected to each other.
Why
Every isolated vertex is its own component; 3 vertices with no edges means 3 separate components.
3
A graph has 8 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 the sum directly: 2|E|=2(8)=16, regardless of how those 8 edges are arranged.
Correct answer
Also accepted:
Why
Apply the handshaking theorem directly to the edge count -- no vertex-by-vertex computation needed.
A graph on 8 vertices has exactly 6 edges, and it's claimed to be connected (1 component). Is that 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.
Edge count isn't arbitrary -- reaching every one of 8 vertices with no repeated connections needs a minimum number of edges, and 6 falls short of it.
Every vertex having degree at least 1 rules out isolated vertices, but it still doesn't guarantee enough edges exist to link all 8 into one connected piece.
Connected graphs need at LEAST n-1 edges, not exactly n -- many connected graphs have far more than n edges.
Why
Connecting n vertices into a single piece needs at least n-1 edges (a tree's worth) -- with 8 vertices that's a minimum of 7. Only 6 edges can connect at most 7 vertices into one piece, leaving at least one vertex stranded.
Think about the fewest edges that could possibly link n vertices into one connected piece, with no edge wasted on a repeat connection.
Compare that minimum edge count, for 8 vertices, against the 6 edges actually given.
No -- a connected graph on 8 vertices needs at least 7 edges, and 6 is one too few