As a matter of fact, that problem is very easy for \epsilon >=1. Take the spanning forest F of the original graph G. Let E be the set of the edges of F and E' the remaining edges of G. The cardinality (number of elements) of E is v-1 >= |E|. So |E'|=2v-|E| >= v+1. Joining each edge of E' to F generates exactly one simple cycle. Then G = E' union F has at least (maybe more since joining 2 edges of E' to F may generate more than 2 simple cycles) |E'| >= v+1 simple cycles. Now each simple cycle is of length at most v and at least 2. The number of distinct lengths is then at most v-1. Therefore there are at least two distinct simple cycles having the same length by the pigeonhole principle (putting p pigeons into h holes where p>b necessarily means there are at least 2 pigeons sharing the same hole).
nightrider 发表评论于 2019-02-28 02:05:13
As a matter of fact, that problem is not too hard for \epsilon >=1. Take the spanning forest F of the original graph G. Let E be the set of the edges of F and E' the remaining edges of G. The cardinality (number of elements) of E is |E|
