CRANATOM - Editorial


CONCEPTS: Graph theory, proof by construction

Problem link

Let the atoms be the nodes and bonds be the edges, then the compound represents a 3D graph.
Now our aim is to construct a 3D graph with n nodes and n+1 edges, such that the girth of the graph is maximised.

You can read about girth of a graph here

Now as there are n+1 edges for n vertices, we will see 2 cycles in the graph. Our aim will be to equalize these cycles. You can prove it mathematically or I will show you a solution by construction: follow the first page of this document for the images.

Hence the answer can be any of (2n+2)/3 or n-n/3 or (2n)/3 +n%3 and several others representing the same form