The difference between odd and even

Computer Science Level 2

In a connected graph with 6 vertices, suppose $x$ vertices have an odd degree, and $y$ vertices have an even degree.

What is the minimum possible value of $\lvert x - y \rvert$ ?

0 4 6 2 3 5 1

1 solution

Pop Wong
Sep 6, 2020

Each edge is connected to two vertices.

The sum of the vertices' degree S should be even such that S/2 is the number of edges in the connected graph.

Therefore, odd degree vertices $x$ is even $= 0,2,4,6$

$x + y = 6 \rightarrow y= 6-x \rightarrow |x-y| = |x-(6-x)| = |2x-6| \implies$ minimum possible value of $\lvert x - y \rvert = 2$ when $x = 2, 4$