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 geta 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, andthere’s only one way to do this. So we’re done.