# Math Help - graph

1. ## graph

suppose G is a connected graph with n vertices and n-1 edges.
prove that G has at least 2 vertices with deg(v)=1 .

3. ## Re: graph

Originally Posted by mshou
suppose G is a connected graph with n vertices and n-1 edges.
prove that G has at least 2 vertices with deg(v)=1 .
Recall that $|\mathcal{V}|$ is the number of vertices and $|\mathcal{E}|$ is the number of edges.

Then we know that $\frac{2|\mathcal{E}|}{|\mathcal{V}|}\ge m$ where $m$ is the minimum vertex degree.

You can use that show that if $|\mathcal{V}|=n-1$ then there must be at one vertex of degree one.

You are working with a connected graph. So all vertices are of degree alt least one.

You should know that $\sum\limits_{v \in\mathcal{V}} {\deg (v)} = 2\left| \mathcal{E} \right|$.

Now you show some effort.