Quiz · Medium
Twenty questions on degrees, Euler and Hamilton circuits, trees, spanning trees, planarity, coloring and traversal.
A tree has 20 vertices. How many edges does it have?
18
19
20
21
A tree on n vertices always has n - 1 edges: 19.
A simple graph has 8 edges. What is the sum of its vertex degrees?
8
12
64
16
Each edge contributes 1 to the degree of each endpoint, so the degree sum is 2 * 8 = 16 (handshake lemma).
How many edges does have?
21
14
42
49
C(7, 2) = 7 * 6 / 2 = 21. 42 counts ordered pairs, which double counts each edge.
Which graph has an Euler circuit?
a path on 5 vertices
A connected graph has an Euler circuit iff all degrees are even. K5 is 4-regular. K4 and K3,3 are 3-regular (odd); a path has two vertices of degree 1.
The Konigsberg bridge graph has vertex degrees 5, 3, 3, 3. Why is there no Euler path?

The graph is disconnected
It has 4 odd-degree vertices, but an Euler path allows at most 2
It contains a vertex of degree 5
It has fewer than 8 edges
An Euler path needs 0 or 2 odd-degree vertices; here all four are odd. The graph is connected, and a degree-5 vertex is fine by itself.
The graph in the picture is

the 6-cycle
Two rows of 3 vertices with every top vertex joined to every bottom vertex: K3,3, with 9 edges. It is bipartite and non-planar. Image: public domain, via Wikimedia Commons.
What is the chromatic number of an odd cycle ?
2
4
7
3
Even cycles are 2-colorable, but with an odd cycle the colors alternate around and clash at the end, so 3 are needed (and enough).
Which statement about bipartite graphs is true?
They contain at least one triangle
They are always trees
They contain no odd cycle
They have an Euler circuit
A graph is bipartite exactly when it has no odd-length cycle. Trees are bipartite but not all bipartite graphs are trees (K3,3 is not).
A connected planar simple graph has V = 6 and E = 9. How many faces does it have?
3
5
4
6
Euler's formula V - E + F = 2 gives F = 2 - 6 + 9 = 5.
Why is not planar?
It has 10 edges, more than 3V - 6 = 9
It has an odd number of vertices
It has no triangles
It is not connected
A simple planar graph on V >= 3 vertices has at most 3V - 6 edges. K5 has 10 > 9.
Prim's and Kruskal's algorithms both produce
a shortest path tree from a source
a maximum matching
an Euler circuit
a minimum spanning tree
Both are greedy algorithms that build a minimum-weight spanning tree. Shortest-path trees come from Dijkstra (they can differ from MSTs).
This weighted graph has its minimum spanning tree in red. What is the weight of the MST?

18
22
20
25
The red edges weigh 1 + 2 + 3 + 3 + 5 + 6 = 20. Image: Illes, public domain, via Wikimedia Commons.
A full binary tree has 15 leaves. How many internal vertices does it have?
7
14
15
16
Leaves = internal + 1 for a full binary tree, so internal = 14 (and 29 vertices in total).
The inorder traversal of the binary tree is

F B A D C E G I H
A C E D B H I G F
F B G A D I C E H
A B C D E F G H I
Inorder visits left subtree, node, right subtree, which gives A B C D E F G H I here. The second option is preorder, the third postorder and the fourth level-order. Image: Moberg, public domain.
Which algorithm finds shortest paths in a graph with non-negative weights?
Dijkstra
Kruskal
Hall's algorithm
Topological sort
Dijkstra's greedy algorithm repeatedly finalizes the nearest unfinished vertex. Kruskal builds an MST.
True or false: every connected graph has a spanning tree.
True
False
Repeatedly delete an edge from any cycle; the graph stays connected and eventually becomes a tree on the same vertices.
Using BFS from vertex 1 (smaller neighbors first) on the graph with edges 1-2, 1-3, 2-4, 2-5, 3-6, 3-7, 5-6, which vertex is visited last?
4
5
7
6
BFS visits level by level: 1; then 2, 3; then 4, 5 (from 2) and 6, 7 (from 3). The order is 1, 2, 3, 4, 5, 6, 7 so 7 is last. The edge 5-6 does not change the levels. (Drawn graph.)
The number of labeled trees on 5 vertices is
125
25
60
3125
Cayley's formula: n^(n-2) = 5^3 = 125.
The graph with two odd-degree vertices (the bottom corners) in the picture has

an Euler circuit
an Euler path but no Euler circuit
neither an Euler path nor an Euler circuit
an Euler circuit but no Euler path
Exactly two vertices have odd degree, so an Euler path exists (from one odd vertex to the other), but no Euler circuit. Image: Fschwarzentruber, CC BY-SA 4.0, via Wikimedia Commons.
A graph has a Hamilton cycle if every vertex has degree at least n/2 (n >= 3). This is
Euler's theorem
Hall's theorem
Dirac's theorem
Kuratowski's theorem
Dirac's theorem gives a sufficient (not necessary) condition for a Hamilton cycle.