Computer Science Engineering (CSE) Exam  >  Computer Science Engineering (CSE) Questions  >  A non-planar graph with minimum number of ver... Start Learning for Free
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
Correct answer is option 'C'. Can you explain this answer?
Verified Answer
A non-planar graph with minimum number of vertices hasa)9 edges, 6 ver...
K5 is smallest non-planar graph in terms of number of vertices.
The number of vertices in K5 is 5 and number of edges in 
View all questions of this test
Most Upvoted Answer
A non-planar graph with minimum number of vertices hasa)9 edges, 6 ver...
To understand why option 'C' is the correct answer, let's first define what a non-planar graph is.

A non-planar graph is a graph that cannot be drawn on a plane without any of its edges crossing. In other words, it is not possible to represent a non-planar graph in a two-dimensional space without any edge intersections.

Now, let's analyze the given options one by one and determine if they satisfy the condition of being a non-planar graph with the minimum number of vertices.

Option A: 9 edges, 6 vertices
- In order to determine if this graph is non-planar, we can use Euler's formula: V - E + F = 2, where V is the number of vertices, E is the number of edges, and F is the number of faces.
- Substituting the given values, we have 6 - 9 + F = 2. Solving this equation, we get F = 5.
- According to Euler's formula, the number of faces in a planar graph is always greater than or equal to the number of edges. In this case, F = 5, which is less than E = 9, indicating that this graph is planar. Therefore, option A is not the correct answer.

Option B: 6 edges, 4 vertices
- Using the same approach as above, we have 4 - 6 + F = 2. Solving this equation, we get F = 4.
- Again, F = 4 is less than E = 6, indicating that this graph is planar. Therefore, option B is not the correct answer.

Option C: 10 edges, 5 vertices
- Applying Euler's formula, we have 5 - 10 + F = 2. Solving this equation, we get F = 7.
- F = 7 is greater than E = 10, indicating that this graph is non-planar. Therefore, option C is the correct answer.

Option D: 9 edges, 5 vertices
- Using Euler's formula, we have 5 - 9 + F = 2. Solving this equation, we get F = 6.
- F = 6 is equal to E = 9, indicating that this graph is planar. Therefore, option D is not the correct answer.

In conclusion, option C (10 edges, 5 vertices) is the correct answer because it represents a non-planar graph with the minimum number of vertices.
Explore Courses for Computer Science Engineering (CSE) exam

Top Courses for Computer Science Engineering (CSE)

A non-planar graph with minimum number of vertices hasa)9 edges, 6 verticesb)6 edges, 4 verticesc)10 edges, 5 verticesd)9 edges, 5 verticesCorrect answer is option 'C'. Can you explain this answer?
Question Description
A non-planar graph with minimum number of vertices hasa)9 edges, 6 verticesb)6 edges, 4 verticesc)10 edges, 5 verticesd)9 edges, 5 verticesCorrect answer is option 'C'. Can you explain this answer? for Computer Science Engineering (CSE) 2024 is part of Computer Science Engineering (CSE) preparation. The Question and answers have been prepared according to the Computer Science Engineering (CSE) exam syllabus. Information about A non-planar graph with minimum number of vertices hasa)9 edges, 6 verticesb)6 edges, 4 verticesc)10 edges, 5 verticesd)9 edges, 5 verticesCorrect answer is option 'C'. Can you explain this answer? covers all topics & solutions for Computer Science Engineering (CSE) 2024 Exam. Find important definitions, questions, meanings, examples, exercises and tests below for A non-planar graph with minimum number of vertices hasa)9 edges, 6 verticesb)6 edges, 4 verticesc)10 edges, 5 verticesd)9 edges, 5 verticesCorrect answer is option 'C'. Can you explain this answer?.
Solutions for A non-planar graph with minimum number of vertices hasa)9 edges, 6 verticesb)6 edges, 4 verticesc)10 edges, 5 verticesd)9 edges, 5 verticesCorrect answer is option 'C'. Can you explain this answer? in English & in Hindi are available as part of our courses for Computer Science Engineering (CSE). Download more important topics, notes, lectures and mock test series for Computer Science Engineering (CSE) Exam by signing up for free.
Here you can find the meaning of A non-planar graph with minimum number of vertices hasa)9 edges, 6 verticesb)6 edges, 4 verticesc)10 edges, 5 verticesd)9 edges, 5 verticesCorrect answer is option 'C'. Can you explain this answer? defined & explained in the simplest way possible. Besides giving the explanation of A non-planar graph with minimum number of vertices hasa)9 edges, 6 verticesb)6 edges, 4 verticesc)10 edges, 5 verticesd)9 edges, 5 verticesCorrect answer is option 'C'. Can you explain this answer?, a detailed solution for A non-planar graph with minimum number of vertices hasa)9 edges, 6 verticesb)6 edges, 4 verticesc)10 edges, 5 verticesd)9 edges, 5 verticesCorrect answer is option 'C'. Can you explain this answer? has been provided alongside types of A non-planar graph with minimum number of vertices hasa)9 edges, 6 verticesb)6 edges, 4 verticesc)10 edges, 5 verticesd)9 edges, 5 verticesCorrect answer is option 'C'. Can you explain this answer? theory, EduRev gives you an ample number of questions to practice A non-planar graph with minimum number of vertices hasa)9 edges, 6 verticesb)6 edges, 4 verticesc)10 edges, 5 verticesd)9 edges, 5 verticesCorrect answer is option 'C'. Can you explain this answer? tests, examples and also practice Computer Science Engineering (CSE) tests.
Explore Courses for Computer Science Engineering (CSE) exam

Top Courses for Computer Science Engineering (CSE)

Explore Courses
Signup for Free!
Signup to see your scores go up within 7 days! Learn & Practice with 1000+ FREE Notes, Videos & Tests.
10M+ students study on EduRev