Thread: Construction

Hi,

I need some help with the following question.

Suppose you have a Laman construction (with the edges and the vertices) that means and for every subset we have . I need to prove there's at least one vertex of degree less then or equal to (a vertex of degree 1 for example is a point that belongs to 1 edge, ...)

Can someone help me with this proof? I tried by saying 'Suppose all of the vertices have degree greater then or equal to 4' and to come to a contradiction, but this didn't work.

Thanks in advance!

This follows from the handshaking lemma.

Questions from graph theory should be posted to Discrete Math subforum.

Originally Posted by emakarov

This follows from the handshaking lemma.

Questions from graph theory should be posted to Discrete Math subforum.

If I suppose that all vertices are of degree greater then or equal to 4 then the sum is at least , but , thus they're not equal, hence a contradiction.

Is there a way to prove it without the handshaking lemma and just by using the two conditions for Laman constructions I gave?