CRANATOM - Editorial

LEVEL: Easy

CONCEPTS: Graph theory, proof by construction

Problem link http://www.codechef.com/CRNM2014/problems/CRANATOM

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 http://en.wikipedia.org/wiki/Girth_(graph_theory)

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