# 2015 Countdown Problem #17: A Graph Theory Problem

Suppose there are 2015 vertices. Let a complete graph on $$n$$ vertices be denoted as $$K_n$$.

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.

×