0
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

By Handshaking Lemma/Degree Sum Formula, the sum of degrees of all vertices is twice the number of edges.

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}

proving the result.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.