Graph with small average degree has two vertices of small degree

152 Views Asked by At

Suppose $G$ is a graph and its average degree $\epsilon(G) = \frac{2|E(G)|}{|V(G)|}$ is in the interval $0 < \epsilon(G) < 2.$ Then clearly $G$ has one vertex of degree at most $1.$

Reading some textbook it says it should in fact have two such vertices. Is this obvious? Somehow I do not see an easy proof of it.

1

There are 1 best solutions below

3
On BEST ANSWER

The result is in fact not true. Suppose there is only one vertex of degree $\leq 1$. Then since the average degree is less than two, there are no vertices of degree $\geq 3$. In other words, we have one vertex with degree $\leq 1$ and all other vertices have degree $2$. Since the sum of the degrees in a graph is always even (as it iss twice the number of edges), the vertex with degree $\leq 1$ has degree $0$. However, this is perfectly possible: for instance consider the disjoint union of a cycle (all whose vertices have degree $2$) and a point: that is an example of a graph having average degree less than $2$, whereas having only one vertex of degree $\leq 1$. (The example is not unique, as we can take the disjoint union of multiple cycles and a point.)