Previous Year Questions: Planar Graph | Engineering Mathematics for Computer Science Engineering - Computer Science Engineering (CSE) PDF Download (2024)

Computer Science Engineering (CSE) Exam>Computer Science Engineering (CSE) Notes>Engineering Mathematics for Computer Science Engineering>Previous Year Questions: Planar Graph

Q1: In an undirected connected planar graph G, there are eight vertices and five faces. The number of edges in G is _________. (2021 SET-1)
(a) 15
(b) 13
(c) 11
(d) 10
Ans:(c)
Sol:Given: For a planner graph G

Number of vertices(V) = 8
Number of region/faces(R/f) = 5
Number of edges(E) = ?

For any planner graph V + F = E + 2

⇒ 8 + 5 = E + 2
⇒ E = 13 − 2 = 11
∴ Number of edges in given graph G is 11.

Q2: Let δ denote the minimum degree of a vertex in a graph. For all planar graphs on n vertices with δ ≥ 3, which one of the following is TRUE? (2014 SET-3)
(a) In any planar embedding, the number of faces is at least (n/2) + 2
(b) In any planar embedding, the number of faces is less than (n/2) + 2
(c) There is a planar embedding in which the number of faces is less than (n/2) + 2
(d) There is a planar embedding in which the number of faces is at most (n/δ+1)
Ans: (a)
Sol: If δ is the minimum degree, given as 3.
Take a vertex of degree3. This vertex has3 edges incident to it.
These3 edges further lead to3 more vertices. Now these vertices can have a minimum degree of3.
We get the following planar graph.

This is the planar graph with minimum degree 3 for each vertex.
From this graph, we can say that 3n ≤ 2e → (1)
As per Euler's formla : n − e + f = 2 ⇒ e = n + f − 2 →(2)
From (1) and (2)
n + f − 2 ≥ (3n/2)
⇒ f ≥ (3n/2) - n + 2
⇒ f ≥ (n/2) + 2 (No of faces is at least ((n/2) + 2).

Q3: Let G be a simple undirected planar graph on 10 vertices with 15 edges. If G is a connected graph, then the number of bounded faces in any embedding of G on the plane is equal to (2012)
(a) 3
(b) 4
(c) 5
(d) 6
Ans: (d)
Sol: For any planar graph,
n(no. of vertices) - e(no. of edges) + f(no. of faces) = 2
f = 15 − 10 + 2 = 7
number of bounded faces = no. of faces -1
= 7 − 1 = 6
So, the correct answer would be D.

Q4: K4 and Q3 are graphs with the following structures
Which one of the following statements is TRUE in relation to these graphs? (2011)
(a) K4 is planar while Q3 is not
(b) Both K4 and Q3 are planar
(c) Q3 is planar while K4 is not
(d) Neither K4 not Q3 is planar
Ans: (b)
Sol: (B) Both are Planar graphs
Both graphs can be drawn on a plane without having any crossed edges.
Showing K₄ is Planar
Showing Q₃ is Planar

Q5: Which of the following statements is true for every planar graph on n vertices? (2008)
(a) The graph is connected
(b) The graph is Eulerian
(c) The graph has a vertex-cover of size at most 3n/4
(d) The graph has an independent set of size at least n/3
Ans: (c)
Sol: Independent Set ≥ ⌈n/k⌉ where,
n is the number of vertices and k is the chromatic number
For anyplanar graph,k ≥ 3andk ≤ 4, therefore, the Independent set is at least⌈n/4⌉.
Hence (D) is false.
Now we know that size of Vertex Cover + Independent Set Number = n.
If Independent set number≥ ⌈n/4⌉then,
Vertex cover≤ n − (n/4)
Vertex Cover ≤ 3n/4
Vertex Cover is at most 3n/4. So, (C) is the correct answer.

Q6: Let G be the non-planar graph with the minimum possible number of edges. Then G has (2007)
(a) 9 edges and 5 vertices
(b) 9 edges and 6 vertices
(c) 10 edges and 5 vertices
(d) 10 edges and 6 vertices
Ans: (b)
Sol: 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.

Q7: Which one of the following graphs is NOT planar? (2005)
(a)(b)(c)(d)Ans: (a)
Sol:We can form a planar graph for all except G1. Hence G1 is not planar graph.

Q8: Let G be a simple connected planar graph with 13 vertices and 19 edges. Then, the number of faces in the planar embedding of the graph is: (2005)
(a) 6
(b) 8
(c) 9
(d) 13
Ans: (b)
Sol: f = e - n + 2 where f denotes number of faces E the number of edges n the number of vertices So f = 19 − 13 + 2 = 8 faces.

The document Previous Year Questions: Planar Graph | Engineering Mathematics for Computer Science Engineering - Computer Science Engineering (CSE) is a part of the Computer Science Engineering (CSE) Course Engineering Mathematics for Computer Science Engineering.

All you need of Computer Science Engineering (CSE) at this link: Computer Science Engineering (CSE)

Engineering Mathematics for Computer Science Engineering

34 videos|114 docs|72 tests

Join Course for Free

Top Courses for Computer Science Engineering (CSE)

GATE Computer Science Engineering(CSE) 2025 Mock Test Series

Question Bank for GATE Computer Science Engineering

General Aptitude for GATE

Computer Networks

Programming and Data Structures

View all

FAQs on Previous Year Questions: Planar Graph - Engineering Mathematics for Computer Science Engineering - Computer Science Engineering (CSE)

1. What is a planar graph?

Previous Year Questions: Planar Graph | Engineering Mathematics for Computer Science Engineering - Computer Science Engineering (CSE) PDF Download (19)

Ans. A planar graph is a graph that can be embedded in the plane in such a way that its edges intersect only at their endpoints.

2. How can you determine if a graph is planar?

Ans. One way to determine if a graph is planar is to use Kuratowski's theorem, which states that a graph is planar if and only if it does not contain a subgraph that is a subdivision of $K_5$ (the complete graph on 5 vertices) or $K_{3,3}$ (the complete bipartite graph on 3 vertices in each part).

3. What are some properties of planar graphs?

Ans. Some properties of planar graphs include: they do not contain $K_5$ or $K_{3,3}$ as minors, they have a linear number of edges in terms of the number of vertices, and their faces can be divided into regions bounded by cycles.

4. Can all graphs be drawn in a planar way?

Ans. No, not all graphs can be drawn in a planar way. Graphs that are not planar are called non-planar graphs.

5. How are planar graphs used in computer science?

Engineering Mathematics for Computer Science Engineering

34 videos|114 docs|72 tests

Join Course for Free

Download as PDF

Explore Courses for Computer Science Engineering (CSE) exam

Top Courses for Computer Science Engineering (CSE)

GATE Computer Science Engineering(CSE) 2025 Mock Test Series

Question Bank for GATE Computer Science Engineering

General Aptitude for GATE

Computer Networks

Programming and Data Structures

Explore Courses

Signup for Free!

Signup to see your scores go up within 7 days! Learn & Practice with 1000+ FREE Notes, Videos & Tests.

Start learning for Free

10M+ students study on EduRev

Extra Questions

past year papers

Previous Year Questions: Planar Graph | Engineering Mathematics for Computer Science Engineering - Computer Science Engineering (CSE)

Exam

Sample Paper

Semester Notes

Summary

video lectures

Previous Year Questions: Planar Graph | Engineering Mathematics for Computer Science Engineering - Computer Science Engineering (CSE)

Previous Year Questions with Solutions

Viva Questions

mock tests for examination

MCQs

Objective type Questions

Important questions

practice quizzes

ppt

study material

Free

pdf

shortcuts and tricks

;

Join with a free account

Get Instant Access to 1000+ FREE Docs, Videos & Tests

10,000,000

Users

100+

Exams

3,25,000

Docs and Videos

75,000

Tests

I have an EduRev Account • Sign Up with Email

Continue

Attempt this test on App!

Get detailed analysis along with solutions of each question.

Open in App

Not Now

"; ht_ml += `

`; $('.adbnr3_tb').html(ht_ml); } else if (catId != null && catId != '' && catId == '48') { var ht_ml = "

UPSC is the most crucial stepping stone for aspirants, and the right platform can make all the difference. Get access to high-quality study material including notes, videos,tests & all famous books summaries along with expert guidance, and a community of like-minded individuals.Take the first step towards success by signing up on EduRev today.

"; ht_ml += `

`; $('.adbnr3_tb').html(ht_ml); } else if (catId != null && catId != '' && catId == '69') { var ht_ml = "

CAT is the most crucial stepping stone to your dream MBA college, and the right platform can make all the difference. Get access to high-quality study material including notes, videos & tests with expert guidance, and a community of like-minded individuals.Take the first step towards success by signing up on EduRev today.

"; ht_ml += `

`; $('.adbnr3_tb').html(ht_ml); } else if (catId != null && catId != '' && catId == '32') { var ht_ml = "

JEE is a crucial stepping stone for IIT aspirants, and the right platform can make all the difference. Get access to high-quality study material including notes, videos & tests along with expert guidance, and a community of like-minded individuals. Take the first step towards success by signing up on EduRev today.

"; ht_ml += `

`; $('.adbnr3_tb').html(ht_ml); } else if (catId != null && catId != '' && parseInt(catId) >= 18 && parseInt(catId) <= 29) { var ht_ml = "

Want to become a " + catName + " topper? The right platform can make all the difference. Get access to high-quality study material including notes, videos, tests & sample papers along with expert guidance, and a community of like-minded individuals. Take the first step towards success by signing up on EduRev today.

"; ht_ml += `

`; $('.adbnr3_tb').html(ht_ml); } else { var ht_ml = "

Are you preparing for " + catName + " Exam? Then you should check out the best video lectures, notes, free mock test series, crash course and much more provided by EduRev. You also get your detailed analysis and report cards along with 24x7 doubt solving for you to excel in " + catName + " exam. So join EduRev now and revolutionise the way you learn!

"; ht_ml += `

`; $('.adbnr3_tb').html(ht_ml); //$(".adbnr3_tb").parent(".cnt_ad_bnr").hide(); //$('.adbnr3_tb').html(""); } $('.adbnr4_tb').html(""); } else { $('.adbnr1_tb').html(""); //$('.adbnr2_tb').html(""); var catId = '12'; var catName='Computer Science Engineering (CSE)'; if (catId != null && catId != '' && catId == '33') { var ht_ml = "

NEET is a crucial stepping stone for aspiring Doctors, and the right platform can make all the difference. Get access to high-quality study material including notes, videos & tests along with expert guidance, and a community of like-minded individuals, Take the first step towards success by signing up for on EduRev today.

"; ht_ml += `

`; $('.adbnr3_tb').html(ht_ml); } else if (catId != null && catId != '' && catId == '48') { var ht_ml = "

"; ht_ml += `

`; $('.adbnr3_tb').html(ht_ml); } else if (catId != null && catId != '' && catId == '69') { var ht_ml = "

"; ht_ml += `

`; $('.adbnr3_tb').html(ht_ml); } else if (catId != null && catId != '' && catId == '32') { var ht_ml = "

"; ht_ml += `

`; $('.adbnr3_tb').html(ht_ml); } else if (catId != null && catId != '' && parseInt(catId) >= 18 && parseInt(catId) <= 29) { var ht_ml = "

"; ht_ml += `

`; $('.adbnr3_tb').html(ht_ml); } else { var ht_ml = "

"; ht_ml += `

`; $('.adbnr3_tb').html(ht_ml); //$(".adbnr3_tb").parent(".cnt_ad_bnr").hide(); //$('.adbnr3_tb').html(""); } $('.adbnr4_tb').html(""); } var hiddenCourseId = $("#hiddenCourseId").val(); if (hiddenCourseId == undefined || hiddenCourseId == null || hiddenCourseId == "") { hiddenCourseId = "0"; } if ('t' != 'v') { showinfinityDocsAdonPage('cont_faqs_before', '12', 'Computer Science Engineering (CSE)', 'Content_page_ad', hiddenCourseId); } else { $(".cont_faqs_before").remove(); } //showinfinityDocsAdonPage('adbnr2_tb', '12', 'Computer Science Engineering (CSE)', 'Content_page_ad', hiddenCourseId); } //$(window).resize(function () { // SetAdBnr(); //}); courseDetailsAd = function () { var _crs_cnt_html = `

`; _crs_cnt_html+="34 videos|114 docs|72 tests"; _crs_cnt_html += `

`; ////debugger; if ('Engineering Mathematics for Computer Science Engineering' != "") { var crd_dtl_ad = "

"; crd_dtl_ad += "

"; crd_dtl_ad += ""; crd_dtl_ad += ""; crd_dtl_ad += ""; crd_dtl_ad += ""; crd_dtl_ad += ""; crd_dtl_ad += "

This doc is part of

Engineering Mathematics for Computer Science Engineering

" + _crs_cnt_html + "

Join course for free

"; crd_dtl_ad += "

"; $(".adbnr2_tb").html(crd_dtl_ad); if ('t' == 'v' && parseInt('0') < 1) { var crd_dtl_ad_1 = "

"; crd_dtl_ad_1 += "

"; crd_dtl_ad_1 += ""; crd_dtl_ad_1 += ""; crd_dtl_ad_1 += ""; crd_dtl_ad_1 += ""; crd_dtl_ad_1 += ""; crd_dtl_ad_1 += "

This video is part of

Engineering Mathematics for Computer Science Engineering

" + _crs_cnt_html + "

Join course for free

"; crd_dtl_ad_1 += "

"; $(".cnt_vd_ttl_btm").after("

" + crd_dtl_ad_1+"

"); } } else { $(".cnt_ad_bnr.are_you_even_banner2").hide(); } } $(document).ready(function () { SetAdBnr(); courseDetailsAd(); });

Previous Year Questions: Planar Graph | Engineering Mathematics for Computer Science Engineering - Computer Science Engineering (CSE) PDF Download (2024)

Engineering Mathematics for Computer Science Engineering

Top Courses for Computer Science Engineering (CSE)

FAQs on Previous Year Questions: Planar Graph - Engineering Mathematics for Computer Science Engineering - Computer Science Engineering (CSE)

Engineering Mathematics for Computer Science Engineering

Top Courses for Computer Science Engineering (CSE)

Extra Questions

past year papers

Previous Year Questions: Planar Graph | Engineering Mathematics for Computer Science Engineering - Computer Science Engineering (CSE)

Exam

Sample Paper

Semester Notes

Summary

video lectures

Previous Year Questions: Planar Graph | Engineering Mathematics for Computer Science Engineering - Computer Science Engineering (CSE)

Previous Year Questions: Planar Graph | Engineering Mathematics for Computer Science Engineering - Computer Science Engineering (CSE)

Previous Year Questions with Solutions

Viva Questions

mock tests for examination

MCQs

Objective type Questions

Important questions

practice quizzes

ppt

study material

Free

pdf

shortcuts and tricks

References