Question 2 [12 marks]
Gallian (2018)1 defines crown graphs as connected, undirected graphs with 2n ≥ 6 vertices that satisfy
the following three properties:
1. n of the vertices form a single, simple cycle (i.e. a cycle with n distinct vertices and n edges)
2. There are no other cycles in the graph
3. Each vertex on the cycle has exactly one pendant edge. Such edges have a vertex from the
cycle on one end and a vertex of degree one at the other end
The following are examples of crown graphs for n = 3, 4, and 5:
(a) Describe in plain English an algorithm that determines whether a graph G of 2n vertices is
a crown graph. Your algorithm must run in O(n) worst-case time. Use the adjacency list
representation of G in your algorithm.
(b) Explain why your algorithm is correct (you do not need to provide a formal proof).
(c) Justify that it runs in the required time. Give as many details as possible.
1Gallian, J. ”Dynamic Survey of Graph Labeling.” Elec. J. Combin. DS6. Dec. 21, 2018
1