Let $G$ be a graph with n vertices and n-1 edges.

Question

Let $G$ be a graph with $n$ vertices and $n-1$ edges.

Prove that $G$ has a vertex that its degree is at most 1.

I thought to assume that all vertices have degree at most 2, so the sum of degrees will be more than $2n$... But I'm not sure I'm in the right direction

Thanks !

Answer 1

It is a well known result that

$$ 2|E(G)| = \sum_{v \in V(G)}d(v) $$

if we have $d(v) \geq 2$ for every vertex $v$, in particular,

$$ 2|E(G)| \geq 2n $$

so $|E(G)| \geq n$. However, our graph has $n-1$ edges, so we've reached a contradiction.