question of graph theory

1 answer below »

Answered Same Day Dec 22, 2021

Solution

Robert answered on Dec 22 2021

122 Votes

Question 4(10 Marks)
Let G be a simple connected planar graph with n (n>4) vertices, m edges and f faces
whose shortest cycle length is six
(a) Use the handshaking lemma for faces and Euler’s formula to prove that
m < 34 (n − 2)
(b) Prove, by contradiction , that G contains at least one vertex of degree 1 or 2
Solution
(a) Use the handshaking lemma for faces and Euler’s formula to prove that
m < ( − )
A graph G is planar, if it can be drawn in the plane in such a way that no two edges
meet except at a vertex with which they are both incident.
Handshaking Lemma for Planar Graphs
In graph theory, a
anch of mathematics, the handshaking lemma is the statement
that every finite undirected graph has an even number of vertices with odd degree. In
more colloquial terms, in a party of people some of whom shake hands, an even
number of people must have shaken an odd number of other people's hands.
In any plane drawing of a planar graph, the sum of the face degrees is equal to twice
the number of edges.(assume V=vertices set, E= Edges set , f=faces set)
deg(v) = 2|E|
.
εV
Each edge has two sides so it contributes exactly 2 to the sum of the face degrees.
Euler’s formula
Euler’s formula relates the number of vertices, edges and faces of a plane drawing of a
planar graph. Every plane drawing of a planar graph divides the...

SOLUTION.PDF

question of graph theory

Solution

Answer To This Question Is Available To Download

Related Questions & Answers

Submit New Assignment