Skip to content
GATETECH
Official PYQ · 2012Q17Graphs: Connectivity, Matching, ColouringMCQ1 mark

GATE CS 2012 Q17 — Graphs: Connectivity, Matching, Colouring

Explain with AI

Let GG be a simple undirected planar graph on 1010 vertices with 1515 edges. If GG is a connected graph, then the number of bounded faces in any embedding of GG on the plane is equal to

Choose one option
View worked solution

Answer: D

According to Euler's formula for any connected planar graph:

V−E+F=2V - E + F = 2

where:

  • VV is the number of vertices,
  • EE is the number of edges, and
  • FF is the total number of faces (which includes both bounded faces and exactly one unbounded/outer face).

Given in the problem:

  • V=10V = 10
  • E=15E = 15

Substituting these values into Euler's formula:

10−15+F=210 - 15 + F = 2 −5+F=2-5 + F = 2 F=7F = 7

Since any planar embedding has exactly 11 unbounded face, the number of bounded faces is:

Fbounded=F−1=7−1=6F_{\text{bounded}} = F - 1 = 7 - 1 = 6

Therefore, the number of bounded faces is 66.

Free practice · Your answers on this page are not saved.

Published
Report a correction
Keep exploringMore Graphs: Connectivity, Matching, Colouring questions