Regular graph

Task number: 4173

Show that if the \( 2k \)-regular graph has an even number of edges, then either \( k \) or \( | V_G | \) is even.

  • Solution

    If we count the degrees, we get twice the total number of edges, that is \( | E_G | = \frac{2k | V_G |}2 = k | V_G | \).

    If both factors were odd, we would get an odd number of edges, which would contradict the assumptions.

Difficulty level: Easy task (using definitions and simple reasoning)
Proving or derivation task
Cs translation
Send comment on task by email