PUMaC 2013 · 组合（B 组） · 第 5 题

PUMaC 2013 — Combinatorics (Division B) — Problem 5

[ 5 ] A sequence of vertices v , v , . . . , v in a graph, where v = v only if i = j and k can be 1 2 k i j any positive integer, is called a cycle if v is attached by an edge to v , v to v , and so on to 1 2 2 3 v connected to v . Rotations and reflections are distinct: A, B, C is distinct from A, C, B and k 1 B, C, A . Suppose a simple graph G has 2013 vertices and 3013 edges. What is the minimal number of cycles possible in G ?

解析

[ 5 ] A sequence of vertices v , v , . . . , v in a graph, where v = v only if i = j and k can be 1 2 k i j any positive integer, is called a cycle if v is attached by an edge to v , v to v , and so on to 1 2 2 3 v connected to v . Rotations and reflections are distinct: A, B, C is distinct from A, C, B and k 1 B, C, A . Suppose a simple graph G has 2013 vertices and 3013 edges. What is the minimal number of cycles possible in G ? 1 Solution We assume G is connected. Then 2012 edges make a spanning subtree of G . Adding any edge is going to allow a new loop; if this loop involves n vertices, 2 n cycles result. Each new edge is going to be involved in at least six new cycles, then, and it can be seen pretty easily that this bound is attained. So the minimum is 6006.