PROBLEM LINKS
DIFFICULTY
HARD
EXPLANATION
It can be shown that G has a cycle of length 5 as a minor iff G has a cycle of length >= 5 in it. So we wish to count biconnected graphs having no cycle of length >= 5.
We start by working out a few special cases for n <= 4. Now, first we show that any biconnected graph having n >= 5 vertices has a cycle of length atleast 4. Consider any nodes u and v which are not connected. Since there are atleast 2 disjoint paths between u and v (each of length >= 2), we can combine them to form a cycle of length >= 4. Hence, the only possibility is that for all u,v there is an edge between then. But in that case, the graph is a clique and has a cycle of length >= 4. Thus, all biconnected components having >= 5 vertices have a cycle.
Now we can use an ear decomposition of two connected graphs. The result basically says that we can start off with any cycle in G, and form the graph progressively by adding maximal paths (ears) to G. So we start off with a cycle having 4 nodes (one surely exists, as we have seen above). Now analysing a few cases reveals that the only way to add ears to G are between 1 diagonal, and each ear should have length exactly 2. In all other cases, we get a cycle of length >= 5. Thus, G looks like this : there are two nodes u and v, with n - 2 disjoint paths of length 2 between them. We can optionally add a direct edge between u and v if needed. Thus, the total number of edges in G are either 2 * (n-2) or 2 * (n-2) + 1. We can choose u and v in ncr(n,2) ways. This gives us the following result :
if n = 1, output 1 if m = 1, else 0
if n = 2, output 1 if m = 1, else 0
if n = 3, output 1 if m = 3, else 0
if n = 4, output 3 if m = 4. If m = 6 output 1, else if m = 5 output 6. else output 0
for n >= 5, output n * (n-1)/2 if m = 2 * (n-2) or m = 2 * (n-2) + 1. else output 0.