search
Log In
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
6 votes
1k views

Choose the correct alternatives ( more than one may be correct) and write the corresponding letters only:

(viii) A non-planar graph with minimum number of vertices has

(a) 9 edges, 6 vertices

(b) 6 edges, 4 vertices

(c) 10 edges, 5 vertices

(d) 9 edges, 5 vertices

in Graph Theory
edited by
1k views

3 Answers

11 votes

A non-planar graph with minimum number of vertices has 10 edges, 5 vertices i.e K5

A non-planar graph with minimum number of edges has 9 edges, 6 vertices i.e K3,3

5 votes
Answer: C
0
Please Explain!
2
k5, k3,3 which are non planner , but k5 with minimum vertex ... 5, so no of edges n(n-1)/2 = 10 edges .
0 votes

Answer: C

Using  Planarity criteria relation  $e \leq 3\times v -6,$

All other option satisfies this relation except option $(C)$

i.e$10 \nleqslant 3 \times 5-6$

0

sir , I think it is not sufficient condition..because  for K3,3 , 9<= 3*6 - 6 but it is non-planar graph..please correct me if I m wrong.. 

Related questions

7 votes
1 answer
1
2.2k views
(x) Maximum number of edges in a planar graph with n vertices is _____
asked Sep 13, 2014 in Graph Theory Kathleen 2.2k views
0 votes
1 answer
2
733 views
Choose the correct alternatives (more than one may be correct) and write the corresponding letters only: Bit-slice processors can be cascaded to get any desired word length processor speed of operation is independent of the word length configured do not contain anything equivalent of program counter in a 'normal' microprocessor Contain only the data path of a 'normal' CPU
asked Sep 13, 2014 in CO and Architecture Kathleen 733 views
22 votes
4 answers
3
7.3k views
Let G be a connected planar graph with 10 vertices. If the number of edges on each face is three, then the number of edges in G is_______________.
asked Feb 14, 2015 in Graph Theory makhdoom ghaya 7.3k views
15 votes
1 answer
4
2.5k views
K4 and Q3 are graphs with the following structures. Which one of the following statements is TRUE in relation to these graphs? K4 is a planar while Q3 is not Both K4 and Q3 are planar Q3 is planar while K4 is not Neither K4 nor Q3 is planar
asked Sep 29, 2014 in Graph Theory jothee 2.5k views
...