2015 Countdown Problem #17: A Graph Theory Problem

Discrete Mathematics Level 3

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.


Problem Loading...

Note Loading...

Set Loading...