Graph Theory Practice Problems with Solutions

12 graph theory practice problems with full solutions: degrees and the handshake lemma, Euler paths, Hamiltonian cycles, minimum spanning trees, Dijkstra’s algorithm, graph coloring and planarity. Each problem has a hint; try it before opening the solution.

Contents5 sections

Facts used in this set

Handshake lemma: the degrees of all vertices add up to twice the number of edges, $\sum \deg(v)=2|E|$ . So the number of odd-degree vertices is always even.
Euler circuit / path (every edge used exactly once) in a connected graph: a circuit exists exactly when every degree is even; a path that is not a circuit exists exactly when exactly two vertices have odd degree, and it must start and end at those two.
Trees: a tree with $n$ vertices has $n-1$ edges.
Planar graphs (simple, connected, $v\ge 3$ ): $e\le 3v-6$ , and $e\le 2v-4$ if there is no triangle. Euler’s formula: $v-e+f=2$ .

Easy problems

Problem 1

Easy

A graph has 7 vertices with degrees 3, 3, 2, 2, 2, 1, 1. How many edges does it have?

Hint

Each edge adds 1 to the degree of each of its two ends.

View Solution

By the handshake lemma, the degree sum is twice the number of edges:

3+3+2+2+2+1+1=14=2|E|,

so $|E|=7$ .

Answer: 7 edges

Problem 2

Easy

Can five people at a party each shake hands with exactly three others?

Hint

Model people as vertices and handshakes as edges. Add up the degrees.

View Solution

The degree sum would be $5\times 3=15$ , an odd number. But the degree sum always equals $2|E|$ , which is even. So such a graph cannot exist.

Answer: No

Problem 3

Easy

In a league of 10 teams, every team plays every other team exactly once. How many games are played?

Hint

This is the number of edges of the complete graph $K_{10}$ .

View Solution

Each game is a pair of teams, so the count is

\binom{10}{2}=\frac{10\cdot 9}{2}=45.

In general $K_n$ has $\frac{n(n-1)}{2}$ edges.

Answer: 45

Problem 4

Easy

A network of 12 computers is connected with cables so that every computer can reach every other one, and there is no loop of cables. How many cables are there?

Hint

Connected and without cycles: what kind of graph is that?

View Solution

A connected graph with no cycle is a tree, and a tree on $n$ vertices has $n-1$ edges. So there are $12-1=11$ cables.

Answer: 11

Medium problems

Problem 5

Medium

The bridges of Königsberg. Four land areas A, B, C, D are joined by 7 bridges: two between A and B, two between A and C, and one each for A–D, B–D and C–D. Can you walk across every bridge exactly once?

Hint

Compute the degree of each land area and count the odd ones.

View Solution

Degrees: $\deg A=5$ , $\deg B=3$ , $\deg C=3$ , $\deg D=3$ . All four are odd. An Euler path allows at most two odd vertices (its start and its end), so no such walk exists. This is the problem Euler solved in 1736, often called the start of graph theory.

Answer: No

Problem 6

Medium

The “house” puzzle. Draw a square with corners A (bottom left), B (bottom right), C (top right), D (top left), both diagonals AC and BD, and a roof: a point E above the square joined to C and D. Can you draw the whole figure without lifting your pen and without retracing a line? If so, where must you start?

Hint

List the 8 edges and the degree of each corner.

View Solution

Edges: AB, BC, CD, DA, AC, BD, CE, DE. Degrees: $\deg A=3$ , $\deg B=3$ , $\deg C=4$ , $\deg D=4$ , $\deg E=2$ .

Exactly two vertices are odd (A and B), so an Euler path exists, but no closed circuit. It must start at one bottom corner and end at the other. One such path:

A → B → D → A → C → D → E → C → B

It uses all 8 edges once each.

Answer: Yes, starting at a bottom corner

Problem 7

Medium

A weighted graph has these edges: A–B 4, A–C 1, B–C 2, B–D 5, C–D 8, C–E 10, D–E 2, D–F 6, E–F 3. Use Kruskal’s algorithm to find a minimum spanning tree and its total weight.

Hint

Sort the edges by weight and add each one unless it closes a cycle. Stop at $6-1=5$ edges.

View Solution

Edges in increasing order, with the decision for each:

Edge	Weight	Decision
A–C	1	add
B–C	2	add
D–E	2	add
E–F	3	add
A–B	4	skip (A–C–B already connects A and B)
B–D	5	add (joins the two pieces); 5 edges, stop

Total weight: $1+2+2+3+5=13$ .

Answer: {A–C, B–C, D–E, E–F, B–D}, weight 13

Problem 8

Medium

In the same weighted graph, use Dijkstra’s algorithm to find the shortest path from A to F.

Hint

Always visit the unvisited vertex with the smallest known distance, then update its neighbors.

View Solution

Visit	Updates
A (0)	B = 4, C = 1
C (1)	B = min(4, 1+2) = 3, D = 9, E = 11
B (3)	D = min(9, 3+5) = 8
D (8)	E = min(11, 8+2) = 10, F = 14
E (10)	F = min(14, 10+3) = 13
F (13)	done

Following the updates back from F: $A\to C\to B\to D\to E\to F$ , length $1+2+5+2+3=13$ . Note that the direct-looking route A–B is longer than going through C.

Answer: A → C → B → D → E → F, length 13

Problem 9

Medium

Find the chromatic number of (a) the 5-cycle $C_5$ , and (b) the wheel formed by $C_5$ plus a center vertex joined to all five.

Hint

Try to color $C_5$ with two colors going around the cycle. What goes wrong?

View Solution

(a) Two colors would have to alternate around the cycle, which needs an even number of vertices. With 5 vertices the last one touches two vertices of different colors, so 2 colors fail. Three colors work: 1, 2, 1, 2, 3. So $\chi(C_5)=3$ .

(b) The center is adjacent to all five rim vertices, so it needs a color not used on the rim. The rim needs 3, so the wheel needs $3+1=4$ .

Answer: (a) 3, (b) 4

Hard problems

Problem 10

Hard

A 3 by 3 grid of points is joined horizontally and vertically to its neighbors. Is there a Hamiltonian cycle (a closed tour visiting every point exactly once)?

Hint

Color the points like a chessboard. What does each step along an edge do to the color?

View Solution

Color the grid points black and white like a chessboard: 5 of one color, 4 of the other. Every edge joins two different colors, so a closed tour alternates colors and must contain as many black points as white points. That forces an even total. The grid has 9 points, an odd number, so no Hamiltonian cycle exists.

The same argument shows that any bipartite graph with an odd number of vertices has no Hamiltonian cycle.

Answer: No

Problem 11

Hard

Show that neither $K_5$ nor $K_{3,3}$ can be drawn in the plane without crossing edges.

Hint

Use the edge bounds for planar graphs. Does $K_{3,3}$ contain a triangle?

View Solution

$K_5$ : $v=5$ , $e=10$ . A planar graph needs $e\le 3v-6=9$ . Since $10>9$ , $K_5$ is not planar.

$K_{3,3}$ : $v=6$ , $e=9$ . Here $3v-6=12$ , so the first bound does not help. But $K_{3,3}$ is bipartite, so it has no triangle, and a triangle-free planar graph needs $e\le 2v-4=8$ . Since $9>8$ , $K_{3,3}$ is not planar.

By Kuratowski’s theorem, these two graphs are the essential obstacles: a graph is planar exactly when it contains no subdivision of $K_5$ or $K_{3,3}$ .

Answer: both violate the planar edge bounds

Problem 12

Hard

How many different trees can be drawn on 5 labeled vertices $1,2,3,4,5$ ?

Hint

There is a famous formula due to Cayley.

View Solution

Cayley’s formula says the number of labeled trees on $n$ vertices is $n^{n-2}$ . For $n=5$ :

5^{3}=125.

You can check it by type: a path uses all 5 vertices in a line ( $5!/2=60$ ), a star has 5 choices of center (5), and the remaining shapes give the other 60. The total is $60+5+60=125$ .

Answer: 125

Frequently asked questions

What is the difference between an Euler path and a Hamiltonian path?

An Euler path uses every edge exactly once; a Hamiltonian path visits every vertex exactly once. Euler paths have a simple degree test; for Hamiltonian paths no fast general test is known.

Do Kruskal’s and Prim’s algorithms give the same tree?

They always give a tree of the same minimum weight. If all edge weights are different, the minimum spanning tree is unique, so they give the same tree.

Does Dijkstra’s algorithm work with negative weights?

No. It assumes that once a vertex is visited its distance is final, which can fail with negative edges. Use the Bellman–Ford algorithm instead.