Quiz · Hard
Fifteen harder graph theory questions: degree sequences, Dirac's theorem, planar edge bounds, tree counting, Hall's theorem, shortest paths and traversals.
A full 3-ary tree has 10 internal vertices. How many leaves?
20
29
21
31
For a full m-ary tree l = (m - 1)i + 1 = 2 * 10 + 1 = 21 (total vertices 31).
A simple graph has degree sequence (4, 4, 3, 3, 2, 2, 2). How many edges does it have, and is the sequence possible?
10 edges; impossible
20 edges; possible
9 edges; possible
10 edges; possible
Sum = 20, so E = 10 (even sum is necessary). Havel-Hakimi: remove 4 -> (3,2,2,1,2,2) -> sorted (3,2,2,2,2,1); remove 3 -> (1,1,1,2,1) -> sorted (2,1,1,1,1); remove 2 -> (0,0,1,1) -> fine. So it is graphical.
A connected simple graph has 12 vertices and every vertex has degree 6. Which theorem guarantees a Hamilton cycle?
Euler's theorem
Cayley's formula
Dirac's theorem
Euler's formula
Each degree 6 = n/2 meets Dirac's condition (degree >= n/2 for n >= 3). Euler's theorem is about edges, not vertices.
A planar graph with 10 vertices has no triangles. The maximum possible number of edges is
16
18
24
27
With no triangles every face has at least 4 edge-sides, so E <= 2V - 4 = 16. The general bound 3V - 6 = 24 applies only if triangles are allowed.
A connected planar graph has all faces bounded by exactly 4 edges (including the outer face). If V = 8, what are E and F?
E = 14, F = 8
E = 12, F = 6
E = 16, F = 10
E = 10, F = 4
4F = 2E gives E = 2F. Euler: 8 - 2F + F = 2 so F = 6, E = 12. This is the cube.
How many distinct Hamilton cycles (undirected, no fixed start) does have?
24
120
60
720
(n - 1)!/2 = 5!/2 = 60.
The chromatic number of the wheel (a 5-cycle plus a hub joined to all rim vertices) is
4
2
3
5
The rim is an odd cycle needing 3 colors, and the hub is adjacent to every rim vertex so needs a 4th.
The Petersen graph (10 vertices, 3-regular) has how many edges and what is its chromatic number?

15 edges; chi = 4
15 edges; chi = 3
30 edges; chi = 3
10 edges; chi = 2
E = 10 * 3 / 2 = 15. It contains 5-cycles so chi >= 3, and the picture shows a 3-coloring. Image: public domain, via Wikimedia Commons.
How many spanning trees does the 4-cycle have?
3
6
16
4
Remove any one of the 4 edges: each gives a distinct spanning path. (By contrast K4 has 4^2 = 16.)
In the weighted graph (edges AB 4, AC 2, BC 1, BD 5, CE 8, DE 2, DF 3, EF 3), the shortest path from A to F has length
9
12
13
11
A-C-B-D-F = 2 + 1 + 5 + 3 = 11. The route via E costs at least 13 (A-C-B-D-E-F = 13 or A-C-E-F = 13).
A tree has exactly 4 vertices of degree 3 and no vertices of degree 2 or more than 3. How many leaves does it have?
6
4
8
10
Let L leaves (degree 1). Degree sum = 12 + L = 2(n - 1) with n = 4 + L, so 12 + L = 2(3 + L) = 6 + 2L, giving L = 6.
Which condition guarantees a bipartite graph with sides X and Y has a matching covering all of X?
every vertex has even degree
for every subset S of X, |N(S)| >= |S|
the graph is a tree
|X| = |Y|
That is Hall's condition, and it is necessary and sufficient. Equal side sizes alone do not help: two vertices may share a single neighbor.
The preorder traversal of the binary tree is

A B C D E F G H I
F B A D C E G I H
A C E D B H I G F
F G B I D A H E C
Preorder visits the root first, then the left subtree, then the right: F, B, A, D, C, E, G, I, H. Image: Moberg, public domain.
The red edges in the picture form a

Hamilton cycle
spanning tree
matching that is maximum
perfect matching
The three red edges share no endpoints, so they form a matching. It is maximum because the upper side has only 3 vertices. It is not perfect since the lower side has 4 vertices, one uncovered. Image: Illes, public domain.
For which n does the complete graph (n >= 3) have an Euler circuit?
only odd n
all n
only even n
only n = 3
Each vertex has degree n - 1, which is even exactly when n is odd.