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 plane is equal to_________.

Question

Prepp Team · Accepted Answer

Understanding Planar Graphs and Faces

The question asks for the number of bounded faces in a specific planar graph G. We are given the number of vertices ($V$), the number of edges ($E$), and that the graph is connected.

Key Information Provided:

Graph Type: Simple, undirected, planar, connected.
Number of Vertices ($V$): 10
Number of Edges ($E$): 15

Applying Euler's Formula for Planar Graphs

For any connected planar graph, Euler's formula establishes a relationship between the number of vertices ($V$), edges ($E$), and faces ($F$) in a planar embedding. The formula is:

$ V - E + F = 2 $

Here, $F$ represents the total number of faces, including the single unbounded face (the region outside the graph).

Calculating the Total Number of Faces (F):

We can plug the given values of $V$ and $E$ into Euler's formula:

$ 10 - 15 + F = 2 $

Simplifying the equation:

$ -5 + F = 2 $

Solving for $F$:

$ F = 2 + 5 $ $ F = 7 $

Therefore, the total number of faces in any planar embedding of graph G is 7.

Calculating Bounded Faces

The total number of faces ($F$) is the sum of the number of bounded faces ($F_{bounded}$) and the one unbounded face ($F_{unbounded}$).

$ F = F_{bounded} + F_{unbounded} $

Since $F_{unbounded} = 1$, we have:

$ F_{bounded} = F - 1 $

Substituting the calculated value of $F$:

$ F_{bounded} = 7 - 1 $ $ F_{bounded} = 6 $

Conclusion

Using Euler's formula, we determined that a connected planar graph with 10 vertices and 15 edges has a total of 7 faces. By subtracting the single unbounded face, we find that the number of bounded faces is 6.