edited by
2,931 views

2 Answers

Best answer
8 votes
8 votes

 A. In complete graph, every vertex should have an edge to all other vertices.

  • In given graph, there is no edge between D and B, A and C.
  • Graph is not complete


B. If nodes in graph can be colored with just two colors, it is bipartitie.

  • Suppose we colored A with red and all neighbours B, D, F with blue.
  • But neighbours B, F and D,F are connected. So they cant have same color.
  • It is not 2 colorable
  • It is not bipartite

C. According to Dirac's theorem, in a graph of n nodes, if each node has degree greater than n/2, graph is Hamiltonian

  • In given graph n =6
  • All nodes have degree =4
  • Hence graph is hamiltonian
  • Sample Hamiltonian path is ABCDEF

Answer: c

edited by
1 votes
1 votes
Answer: OPTION C
OPTION A is false because for a complete graph with n vertices , should be n(n-1)/2 edges . But here for 6 vertices , no. of edges=13 !=  [6(6-1)/2=] 15
for bipartite graph at least two partition should be there with (m,n) vertices , but there is no partition possible. so option B is false

for Hamiltonian graph refer point 3.6 from this pdf :-   http://compalg.inf.elte.hu/~tony/Oktatas/TDK/FINAL/Chap%203.PDF
Please check
Answer:

Related questions

2 votes
2 votes
1 answer
1
makhdoom ghaya asked Jul 24, 2016
1,564 views
Match the following $:$ $\begin{array}{clcl} & \textbf{List – I} && \textbf{List – II} \\ \text{a.} & \text{Call Control protocol} &\text{i.} & \text{Interface b...
0 votes
0 votes
1 answer
2
makhdoom ghaya asked Jul 23, 2016
1,129 views
________ model is designed to bring prices down by increasing the number of customers who buy a particular product at once.Economic Order QuantityInventory Data MiningDem...
0 votes
0 votes
3 answers
3
makhdoom ghaya asked Jul 23, 2016
3,324 views
Which e-business model allows consumers to name their own price for products and services ? $B2 B$$B2 G$ $C2 C$ $C2 B$
1 votes
1 votes
1 answer
4
makhdoom ghaya asked Jul 23, 2016
2,375 views
Fact-less fact table in a data warehouse containsOnly measuresOnly dimensionsKeys and measuresOnly surrogate keys