0
25kviews
Determine the number of edges in a graph with 6 nodes, 2 nodes of degree 4 and 4 nodes of degree 2. Draw two such graphs.
1 Answer
written 8.0 years ago by | • modified 8.0 years ago |
$\text{Suppose the graph with 6 vertices has e number of edges. Therefore by Handshaking Lemma}$
$$\sum^6_{i=1}\deg(v_i)=2e$$
$\Rightarrow d(v_1)+d(v_2)+d(v_3)+d(v_4)+d(v_5)+d(v_6)=2e$
$\text{Now, given 2 vertices are of degree 4 and 4 vertices are of degree2.} \\ \text{Hence the above equation,}$
$\hspace{2cm}(4+4)+(2+2+2+2)=2e \\ \Rightarrow \hspace{5.4cm}16=2e \hspace{2cm} \Rightarrow e=8$
$\text{Hence the number of efges in a graph with 6 vertices with given condition is 8.} \\ \text{Two such graphs are shown below in figure}$