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**

0

20kviews

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

1

1.9kviews

written 7.5 years ago by |

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

ADD COMMENT
EDIT

Please log in to add an answer.