Let be a positive integer. Show that if a graph has no cycles of length at most , then it has at most cycles of length exactly , where denotes the number of vertices in the graph G.
Solution
The key idea is that there is at most 1 path of length between any pair of vertices, or else you get a cycle of length . Now, start at any vertex ( choices) and walk 2015 times. There's at most ways to do this by the previous argument. Now you have to go from the end to the start, and there's only one way to do this. So we're done.
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.