Question

Which one of the following graphs admits an Eulerian cycle? K2019,2020 K1000 the four other possible answers are incorrect K2.1001 K4,1000

Answer 1

Euler's Theorem states that a graph admits an Eulerian Cycle if and only if each of its vertices is of even degree.


K_2019,2020 is a complete bipartite graph whose vertex sets V₁ and V₂ are of cardinalities 2019 and 2020 respectively.
Observe that if v $\in$ V₂, then v is adjacent to all the 2019 vertices of V₁. Thus, degree of v is 2019. Since v has odd degree, hence by Euler's Theorem, K_2019,2020 doesn't admit an Eulerian cycle.

Again, K₁₀₀₀ is a complete graph with 1000 vertices. Thus, every vertex is adjacent to the rest of the 999 vertices. Hence, the degree of every vertex is 999. Therefore, there is at least one vertex of odd degree. Hence, by Euler's Theorem, K₁₀₀₀ doesn't admit an Eulerian Cycle.

Again, K_2,1001 is a complete bipartite graph whose vertex sets V₁ and V₂ are of cardinalities 2 and 1001. Choose a vertex v in V₁. Then, v is adjacent to each of the 1001 vertices of V₂. Thus, degree of v is 1001, which is odd. Again, by Euler's Theorem, K_2,1001 doesn't admit an Eulerian Cycle.

Observe however, that every vertex of K_4,1000 has even degree. To see this, suppose that the vertex set of K_4,1000 is partitioned as V₁$\cup$ V₂ where V₁ has 4 vertices and V₂ has 1000 vertices. Thus, every vertex of the graph is in V₁ or V₂ . Now, every vertex in V₁ has degree 1000 and every vertex in V₂ has degree 4. Hence, all vertices in the graph are of even degree. Thus, by Euler's Theorem, K_4,1000 admits an Eulerian Cycle.

Hence, the answer is K_4,1000