# graph

• May 27th 2013, 12:45 PM
mshou
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 .
• May 27th 2013, 02:24 PM
emakarov
Re: graph
• May 27th 2013, 02:35 PM
Plato
Re: graph
Quote:

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.