# Construction

• March 19th 2013, 08:56 AM
Siron
Construction
Hi,

I need some help with the following question.

Suppose you have a Laman construction $F=(E,V)$ (with $E$ the edges and $V$ the vertices) that means $E=2V-3$ and for every subset $E'$ we have $e' \leq 2v'-3$. I need to prove there's at least one vertex of degree less then or equal to $3$ (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.

• March 19th 2013, 11:57 AM
emakarov
Re: Construction
This follows from the handshaking lemma.

Questions from graph theory should be posted to Discrete Math subforum.
• March 20th 2013, 07:49 AM
Siron
Re: Construction
Quote:

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 $v$ vertices are of degree greater then or equal to 4 then the sum is at least $\sum_{v \in v} \mbox{deg}(v) = 4v$, but $2|E|=2(2v-3) =4v-6$, 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?