Finding quantity of vertex of odd degree in a graph

Question

Let $G=(V,X)$. If $G$ has n vertex, such exactly $n-1$ have odd degree, how many vertex of odd degree have $\overline {G}$.

($\overline {G}$ the complement of $G$.)

So the first thing I notice is that $n$ has to be an odd number, because it's impossible to have a pair number of vertex of odd degree.

So then I tried to find some pattern, so then I could use it as an inductive hypothesis, but I get:

$n=1 \rightarrow 0$ vertex of odd degree.

$n=3 \rightarrow 1$ vertex of odd degree.

$n=3 \rightarrow 4$ vertex of odd degree.

Tried to do for $n=5$ but it stops to be trivial how to make the graph, and how to count the odd edges.

I can't think of any other way to start the problem, could you give me a hint?

Answer 1

The key is that there are $n=2l+1$ vertices, an odd number. The degree of every vertex in $K_n$ is $2l$ which is even and so if $v$ has odd degree in $G$ then $v$ also has odd degree in $\overline{G}$.

Thus there are $n-1$ vertices of odd degree in $\overline{G}$.

We can verify this by considering the complete bipartite graph $H:=K_{1,2l}$ which has $n=2l+1$, $n-1=2l$ vertices of degree 1 (which is odd) and 1 vertex of degree $2l$ which is even. The complement of $H$ is $K_1 \cup K_{2l}$ which has 1 vertex of degree 0 (even) and $2l$ of degree $2l-1$ (which is odd). Here's an example in Maple:

Answer 2

As you noticed $n$ is odd.

If $v_{i}$ is a vertex in $G$ with odd degree, then in $\overline{G}$ $v_{i}$ has odd degree, because the difference of an even number and an odd number is odd.

Similarly if $v_{i}$ is a vertex in $G$ with even degree, then in $\overline{G}$ $v_{i}$ has even degree.

So the number of vertex of odd degree in $\overline{G}$ is equale to the number of vertex of odd degree in $G$, namely $n-1$