Graph G =(V,E) contains two vertices of degree 1 and, for every k∈2,...,n−1, exactly one vertex of degree k. Show that n cannot be a multiple of 4.

Question

Let $G = (V, E)$ be a simple undirected graph of n vertices.

Suppose that $G$ contains two vertices of degree 1 and, for every $k ∈ \{2, . . . , n − 1\}$, exactly one vertex of degree $k$. Show that $n$ cannot be a multiple of 4.

I tried to use the degree-vertex relation but didn't help.

$$\sum deg(v) = 2 |E|$$

Answer 1

Suppose that $n=4b$ where $b$ is an integer.

$\sum deg(v) =\frac{(n-2)(n+1)}{2}+2= 2 |E|$

Now $n-2=2k$ where $k$ is an odd integer, also $n+1=2k+3$

So we'll have, $2k(2k+3)=4(|E|-1) \implies k(2k+3)=2(e-1)$

That is a contradiction since $k$ is odd and $2k+3$ is odd and the multiplication of 2 odd numbers is odd, but at the R.H.S is even.

Answer 2

Using the degree-vertex property $$\sum deg(v) = 1 + 2 + 3 +... +n-1 + 1 = 1 + \frac{(n-1)(n)}{2}$$

Now, if $n$ is a multiple of 4, then this sum is odd, which is not possible as it must be equal to $2|E|$