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, 12:45 PMmshougraph
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 PMemakarovRe: graph
Use the handshaking lemma.

- May 27th 2013, 02:35 PMPlatoRe: graph
Recall that is the number of vertices and is the number of edges.

Then we know that where is the minimum vertex degree.

You can use that show that if 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 .

Now you show some effort.