# 2015 Countdown Problem #17: A Graph Theory Problem

**Discrete Mathematics**Level 3

Which statements are true?

I. \(K_{2015}\) has 2029105 edges.

II. Suppose two \(K_{2015}\) graphs are connected together, by having exactly one edge connected between any vertex in each of the original \(K_{2015}\) graphs, to form a new graph \(G_{2015}\). Then \(G_{2015}\) is bipartite.

III. Let \(H_{2014}\) be a complete 2014-partite graph on \(2014^2\) vertices, such that the number of vertices in each partition are equal. Then \(K_{2015}\) is not a subgraph of \(H_{2014}\).

*This problem is part of the set 2015 Countdown Problems.*