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) 10Ans:**(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) 6Ans:** (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 structuresWhich 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 planarAns**: (b)

**Sol:**(B) Both are Planar graphs

Both graphs can be drawn on a plane without having any crossed edges.

Showing K

_{4}is Planar

Showing Q

_{3}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)

(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:

**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 verticesAns:** (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) 13Ans:** (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 Engineering34 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? |

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? |

Ans. Planar graphs are used in various applications in computer science, such as in designing efficient algorithms, network routing, and map coloring problems. Their properties make them a useful tool in solving complex problems efficiently.

**Related Exams**

Computer Science Engineering (CSE)

**About this Document**

Sep 02, 2024 Last updated |

**Document Description: **Previous Year Questions: Planar Graph for Computer Science Engineering (CSE) 2024 is part of Engineering Mathematics for Computer Science Engineering preparation. The notes and questions for Previous Year Questions: Planar Graph have been prepared according to the Computer Science Engineering (CSE) exam syllabus. Information about Previous Year Questions: Planar Graph covers topics like and Previous Year Questions: Planar Graph Example, for Computer Science Engineering (CSE) 2024 Exam. Find important definitions, questions, notes, meanings, examples, exercises and tests below for Previous Year Questions: Planar Graph.

Introduction of Previous Year Questions: Planar Graph in English is available as part of our Engineering Mathematics for Computer Science Engineering for Computer Science Engineering (CSE) & Previous Year Questions: Planar Graph in Hindi for Engineering Mathematics for Computer Science Engineering course. Download more important topics related with notes, lectures and mock test series for Computer Science Engineering (CSE) Exam by signing up for free. Computer Science Engineering (CSE): Previous Year Questions: Planar Graph | Engineering Mathematics for Computer Science Engineering - Computer Science Engineering (CSE)

Description

Full syllabus notes, lecture & questions for Previous Year Questions: Planar Graph | Engineering Mathematics for Computer Science Engineering - Computer Science Engineering (CSE) - Computer Science Engineering (CSE) | Plus excerises question with solution to help you revise complete syllabus for Engineering Mathematics for Computer Science Engineering | Best notes, free PDF download

Information about Previous Year Questions: Planar Graph

In this doc you can find the meaning of Previous Year Questions: Planar Graph defined & explained in the simplest way possible. Besides explaining types of Previous Year Questions: Planar Graph theory, EduRev gives you an ample number of questions to practice Previous Year Questions: Planar Graph tests, examples and also practice Computer Science Engineering (CSE) tests

| ## Engineering Mathematics for Computer Science Engineering34 videos|114 docs|72 tests |

Join Course for Free

Download as PDF

Download as PDF

### 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

Related Searches

## 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

,

,

## 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

Attempt this test on App!

Get detailed analysis along with solutions of each question.

Open in App

Not Now

"; ht_ml += `

Sign up for Free Download App for Free

`; $('.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 += `

Sign up for Free Download App for Free

`; $('.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 += `

Sign up for Free Download App for Free

`; $('.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 += `

Sign up for Free Download App for Free

`; $('.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 += `

Sign up for Free Download App for Free

`; $('.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 += `

Sign up for Free Download App for Free

`; $('.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 += `

Sign up for Free Download App for Free

`; $('.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 += `

Sign up for Free Download App for Free

`; $('.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 += `

Sign up for Free Download App for Free

`; $('.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 += `

Sign up for Free Download App for Free

`; $('.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 += `

Sign up for Free Download App for Free

`; $('.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 += `

Sign up for Free Download App for Free

`; $('.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 | 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 | 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(); });