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

$\text{By the Handshaking Lemma we get}$

$$\sum^n_{i=1}d((v_i)=2e=2 \times 6$$

$Or,\hspace{2.5cm} d(v_1)+d(V_2)+....+d(v_n)=2 \times 6=12 \\ Or, \hspace{4.6cm}2+2+....+2=12 \\ Or, \hspace{6.7cm}2n=12\Rightarrow n=6$

$\text{Hence, 6 nodes are necessary to construct a graph with 6 edges in which each vertex is of degree 2.}$

Please log in to add an answer.