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

0

4.4kviews

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

written 7.4 years ago by

teamques10 ★ 65k

modified 2.3 years ago by

pedsangini276 • 4.8k

Mumbai University > Computer Engineering > Sem 3 > Discrete Structures

Marks: 5 Marks

Year: Dec 2014

discrete mathematics

ADD COMMENT EDIT

1 Answer

0

362views

written 7.4 years ago by

teamques10 ★ 65k

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

ADD COMMENT EDIT

Please log in to add an answer.