0

21kviews

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

written 7.9 years ago by teamques10 ★ 68k

modified 2.9 years ago by sagarkolekar ★ 11k

discrete mathematics

ADD COMMENT FOLLOW SHARE EDIT

1 Answer

1

2.0kviews

written 7.9 years ago by teamques10 ★ 68k

$\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 SHARE EDIT