retagged by
10,108 views

3 Answers

Best answer
22 votes
22 votes
ans is B:

non planar graph with smallest number of edges is K3,3; it has 9 edges and 6 vertices

K5 is also non planar but it has 10 edges and 5 vertices.
selected by
5 votes
5 votes
In planar graph, any face (except possibly the outer line) is bounded by atleast three edges and every edge touches atmost two faces.
Using Euler’s formula it states that,
if v ≥ 3 then e ≤ 3v-6
where e=edges
v=vertices
Go through the options
i) 9e and 5v ⇒ 9≤3(5)-6
⇒ 9≤15-6
⇒ 9≤9 (It’s satisfies planar graph)
ii) 9e and 6v ⇒ 9≤3(6)-6
⇒ 9≤12 (It’s planar graph)
iii) 10e and 5v ⇒ 10≤3(5)-6
⇒ 10≤9 (It’s not satisfies planar graph condition)
So, option C is non-planar graph.
iv) 10e and 6v ⇒ 10≤3(6)-6
⇒ 10≤12 (It’s planar graph)
–1 votes
–1 votes
We can check it with Euler's formula V - e + r = 2 and 3r $\leq$ 2e.
Take each option and check whether 3r $\leq$ 2e after finding value of r using
v - e + r = 2.
if its satisfies the condition than its is planar otherwise not.
For all option its satisfies except option c
Answer:

Related questions

1 votes
1 votes
0 answers
1
Kathleen asked Sep 21, 2014
989 views
Consider the series $x_{n+1} = \frac{x_n}{2}+\frac{9}{8x_n},x_0 = 0.5$ obtained from the Newton-Raphson method. The series converges to1.5$\sqrt{2}$1.61.4
76 votes
76 votes
5 answers
2
Kathleen asked Sep 21, 2014
25,056 views
Which of the following graphs has an Eulerian circuit?Any $k$-regular graph where $k$ is an even number.A complete graph on $90$ vertices.The complement of a cycle on $25...
11 votes
11 votes
1 answer
3
28 votes
28 votes
6 answers
4
go_editor asked Feb 12, 2015
12,761 views
A graph is self-complementary if it is isomorphic to its complement. For all self-complementary graphs on $n$ vertices, $n$ isA multiple of 4EvenOddCongruent to 0 $mod$ 4...