# The number of degree one and degree three vertices in a graph with no isolated vertices and with more vertices than edges

Someone asked me this a few days ago:

Let $$G=(V, E)$$ be a graph and denote the set of vertices with degree $$i$$ by $$V_i$$. If $$|V_0|=0$$ and $$|V_3| > |V_1|$$, prove that $$|V| < |E|$$.

Is there a more concise proof than the following one:

Consider the graph $$G=(V, E)$$ with a nonzero minimum degree and such that $$|E| \leq |V|$$. We will show that $$|V_1| \geq |V_3|$$.

1. If $$|E|<|V|-1$$ then $$G$$ has more than one component. We can use the following arguments for each component.
2. If $$|E|=|V|$$ then $$G$$ is a cycle. Thus $$|V_1| = |V_3| = 0$$.
3. If $$|E|=|V|-1$$ then $$G$$ is a tree. Note that if $$v\in V_1$$ then $$v$$ cannot be adjacent to another element of $$V_1$$ because this means the graph is not connected (the edge between these vertices contributes the entirety of each vertices's degrees, implying they can't be adjacent to any other vertices). Now consider the graph $$G_2 =G \setminus \{ V_2\}$$, where we delete from $$G$$ the vertices with degree 2 and the edges incident to these deleted vertices. If $$v \in V_1$$ were adjacent to a vertex in $$V_2$$ in $$G$$, then $$v$$ will be an isolated vertex in $$G_2$$ (degree 0). The remaining vertices in $$V_1$$ are adjacent to vertices in $$V_3 \cup V_4 \cup \dots \cup V_{max \ degree}$$. Thus these remaining vertices in $$V_1$$ (via the edges incident to these vertices) have a one-to-one correspondence to vertices in $$V_3 \cup V_4 \cup \dots \cup V_{max \ degree}$$. If we count the number of these edges (in $$G_2$$) incident to vertices in $$V_1$$ and add the number of isolated vertices in $$G_2$$, we have $$|V_1| \geq |V_3 \cup V_4 \cup \dots \cup V_{max \ degree}| \geq |V_3|.$$

After giving the previous proof to the person who asked me about it, I am wondering if there is a shorter proof for this? Maybe an algorithmic one or a probabilistic one. Or is there a shorter and more direct way to prove the statement?

Let $$|V|$$ be the total number of vertices. We have:
\begin{align}2|E| = \sum_{v\in V}\deg(v)=\sum_{i\ge 0} i|V_i|&= \sum_{i \ge 4}i|V_i|+3|V_3| + 2|V_2| + |V_1| \\&> 2\sum_{i\ge 4}|V_i|+2|V_3|+|V_1|+2|V_2|+|V_1|\\&=2\sum_{i\ge 1} |V_i| = 2|V|\end{align}