Let G be a connected planar graph with 10 vertices. If the number of edges on each face is three, then the number of edges in G is ________.Correct answer is '24'. Can you explain this answer?

Question

Answer

Explanation:
To find the number of edges in the connected planar graph G with 10 vertices, given that the number of edges on each face is three, we can use Euler's formula for planar graphs.

Euler's Formula:
For a connected planar graph with V vertices, E edges, and F faces, the formula is given by:
V - E + F = 2

Given Information:
- Number of vertices (V) = 10
- Number of edges on each face = 3

Calculating the number of faces:
Each face in the graph has 3 edges. Since each edge is shared by 2 faces, the total number of edges is counted twice when calculating the number of faces. Therefore, the number of faces (F) can be calculated as:
F = E/2

Applying Euler's Formula:
Substitute the given information into Euler's formula:
10 - E + E/2 = 2
Simplify the equation:
10 + E/2 = 2
E/2 = -8
E = -16

Calculating the number of edges:
Since the number of edges cannot be negative, we made an error in the calculations. Let's correct it.

Correcting the Calculation:
We know that the number of edges on each face is 3. Therefore, the total number of edges is equal to 3 times the number of faces:
E = 3F
Substitute the value of F:
E = 3(E/2)
E = 3E/2
2E = 3E
E = 2E
Therefore, the number of edges in the connected planar graph G with 10 vertices is 24.

Answer

Data:
number of faces = |F|
number of vertices = |V| = 10
edges covering each face = 3

Formula:
According to Euler’s formula :
|V| - |E| + |F| = 2

Calculation
edges on each face is three
∴ 2 |E| = 3 |F| (every edge is shared by 2 faces)

the number of edges in G is 24

Similar Civil Engineering (CE) Doubts

If a graph (G) has no loops or parallel edges and if the number of vertices(n) in the graph is n≥3, then the graph G is Hamiltonian if(i) deg(v) ≥n/3 for each vertex v(ii) deg(v) + deg(w) ≥ n whenever v and w are not connected by an edge.(iii) E (G) ≥ 1/3 (n - 1)(n - 2) + 2

If a graph (G) has no loops or parallel edges and if the number of vertices(n) in the graph is n≥3, then the graph G is Hamiltonian if(i) deg(v) ≥n/3 for each vertex v(ii) deg(v) + deg(w) ≥ n whenever v and w are not connected by an edge.(iii) E (G) ≥ 1/3 (n - 1)(n - 2) + 2

Let G = (V, E) be a directed graph where V is the set of vertices and E the set of edges. Then which one of the following graphs has the same strongly connected components as G?

Let G1 and G2 be two edge disjoint and vertex disjoint graphs. G1 has 4 vertices and 6 edges, G2 has 6 vertices and 10 edges. Then number of edges in (G1 intersection G2) and (G1 union G2) are respectively

Which of the properties hold for the adjacency matrix A of a simple undirected unweighted graph having n vertices?

Top Courses for Civil Engineering (CE)View all

General Aptitude for GATE

GATE Civil Engineering (CE) 2025 Mock Test Series

Fluid Mechanics for Civil Engineering

General Awareness & Knowledge

Topicwise Question Bank for Civil Engineering

Top Courses for Civil Engineering (CE)

Top Courses for Civil Engineering (CE)

Suggested Free Tests

Related Content

Mock Test Series

Subject-wise Courses

Subject-wise Courses

Other Engg Branches

Company