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 .

Printable View

- May 27th 2013, 11:45 AMmshougraph
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, 01:24 PMemakarovRe: graph
Use the handshaking lemma.

- May 27th 2013, 01:35 PMPlatoRe: graph
Recall that $\displaystyle |\mathcal{V}|$ is the number of vertices and $\displaystyle |\mathcal{E}|$ is the number of edges.

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

You can use that show that if $\displaystyle |\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 $\displaystyle \sum\limits_{v \in\mathcal{V}} {\deg (v)} = 2\left| \mathcal{E} \right|$.

Now you show some effort.