Mumbai University > Computer Engineering > Sem 3 > Discrete Structures

Marks: 5 Marks

Year: Dec 2014

$\text{Suppose these are P vertices in the graph with 6 degree. Also given the degree of each vertex is 2.} \\ \text{By handshaking lemma,}$

$$\sum^P_{i=1}\deg (v_i)=2q=2 \times 6$$

$\Rightarrow d(v_1)+d(v_2)+....+d(v_n)=12 \\ \Rightarrow \hspace{2cm}2+2+....+2=12 \\ \Rightarrow \hspace{4cm}2P=12 \hspace{1.5cm} \Rightarrow P=6 \text{vertices are needed.}$