0
4.6kviews
How many vertices are necessary to construct a graph with exactly 6 edges in which each vertex is of degree 2.

Mumbai University > Computer Engineering > Sem 3 > Discrete Structures

Marks: 5 Marks

Year: Dec 2014

1 Answer
0
373views

$\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.}$

Please log in to add an answer.