This follows from the handshaking lemma.
Questions from graph theory should be posted to Discrete Math subforum.
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.
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?