HMMT 二月 2017 · 团队赛 · 第 6 题
HMMT February 2017 — Team Round — Problem 6
题目详情
- [ 40 ] Let r be a positive integer. Show that if a graph G has no cycles of length at most 2 r , then it has 2016 at most | V | cycles of length exactly 2016 r , where | V | denotes the number of vertices in the graph G .
解析
- [ 40 ] Let r be a positive integer. Show that if a graph G has no cycles of length at most 2 r , then it has 2016 at most | V | cycles of length exactly 2016 r , where | V | denotes the number of vertices in the graph G . Proposed by: Yang Liu The key idea is that there is at most 1 path of length r between any pair of vertices, or else you get a cycle of length ≤ 2 r. Now, start at any vertex ( | V | choices) and walk 2015 times. There’s at most 2016 | V | 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.