Extend the Euler’s formula: n m + f = 2 for connected planar graphs, to incorpor

Question

Extend the Euler’s formula:

n m + f = 2

for connected planar graphs, to incorporate the number of connected components k, along with the number of nodes n, the number of edges m, and the number of faces f

Hint : For connected graphs we have k = 1, what if a graph is disconnected? A possible approach for k > 1 connected components: Let G1, . . . , Gk be the connected components, for k > 1. Let Gi have ni nodes, mi edges, and fi faces, when Gi is considered in isolation as a “whole graph.” We can apply the formula for connected graphs to each connected component Gi to obtain k identities ni mi + fi = 2 (5) for i = 1, . . . , k. We need to combine these “small” identities (5) somehow to obtain one “big” identity that involves all the numbers n, m, f , k.

This is Discrete Structures class, help me please. Thank you

Explanation / Answer

Let G be a plane drawing of a connected plannar graph , and let n,m, and f denote respectively the number of vertices,edges and faces of G . Then

n-m+f=2

where n=11 , m=13 and f=4 and n-m+f=11-13+4=2

Proof :-

The proof is by induction on the number of edges G. if m=0 and then n=1 and f=1 .(infinite case) the theorem is therefore true in this case.

Now suppose that the theorem holds for all graphs with at most m-1 edges and G be a graph with m edges.

if G is a tree then m=n-1 and f=1, so that n-m+f=2 required.if G is not a tree , let e be an edge in some cycle of G.

Then G-e is a connected plane Graph with n vertices , m-1 edges and f-1 faces, so that

n-(m-1)+(f-1)=2 , by the induction hypothesis , it follows that n-(m-1)+(f-1)=2 , by the induction of hypothesis . it follws that n-m+f=2 required.

This result is often called as Eulers polyhedron formula.,since it relates the number of vertices , edges and faces of a convex polyhedron.

Example : cube we have n=8, m=12,f=6 and n-m+f=8-12+6=2 . (draw cube picture)

and one more diagram is there i am unable draw here . so that's why i couldn't draw here.

Related Questions

Navigate

• Browse (All)
• Browse E
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.