Graph Theory - Lecture 16 Notes

: Graph Theory - Lecture 16 Notes

 Page 1


Graph Theory: Lecture No. 16
Graph Theory: Lecture No. 16
L. Sunil Chandran
Computer Science and Automation,
Indian Institute of Science, Bangalore
Email: sunil@csa.iisc.ernet.in
Page 2


Graph Theory: Lecture No. 16
Graph Theory: Lecture No. 16
L. Sunil Chandran
Computer Science and Automation,
Indian Institute of Science, Bangalore
Email: sunil@csa.iisc.ernet.in
Graph Theory: Lecture No. 16
Let G be a graph with maximum degree ¢.
Then ¢·Â
0
(G)· ¢+1.
Page 3


Graph Theory: Lecture No. 16
Graph Theory: Lecture No. 16
L. Sunil Chandran
Computer Science and Automation,
Indian Institute of Science, Bangalore
Email: sunil@csa.iisc.ernet.in
Graph Theory: Lecture No. 16
Let G be a graph with maximum degree ¢.
Then ¢·Â
0
(G)· ¢+1.
Graph Theory: Lecture No. 16
A graph drawn on the plane in such way that
no two edges intersect other than at the end
points is called a plane graph. Abstract graphs
that can be drawn in this way are called
planar.
Page 4


Graph Theory: Lecture No. 16
Graph Theory: Lecture No. 16
L. Sunil Chandran
Computer Science and Automation,
Indian Institute of Science, Bangalore
Email: sunil@csa.iisc.ernet.in
Graph Theory: Lecture No. 16
Let G be a graph with maximum degree ¢.
Then ¢·Â
0
(G)· ¢+1.
Graph Theory: Lecture No. 16
A graph drawn on the plane in such way that
no two edges intersect other than at the end
points is called a plane graph. Abstract graphs
that can be drawn in this way are called
planar.
Graph Theory: Lecture No. 16
Euler's Formula: Let G be a connected plane
graph with n vertices, m edges and ` faces.
Then n¡m+` = 2.
Page 5


Graph Theory: Lecture No. 16
Graph Theory: Lecture No. 16
L. Sunil Chandran
Computer Science and Automation,
Indian Institute of Science, Bangalore
Email: sunil@csa.iisc.ernet.in
Graph Theory: Lecture No. 16
Let G be a graph with maximum degree ¢.
Then ¢·Â
0
(G)· ¢+1.
Graph Theory: Lecture No. 16
A graph drawn on the plane in such way that
no two edges intersect other than at the end
points is called a plane graph. Abstract graphs
that can be drawn in this way are called
planar.
Graph Theory: Lecture No. 16
Euler's Formula: Let G be a connected plane
graph with n vertices, m edges and ` faces.
Then n¡m+` = 2.
Graph Theory: Lecture No. 16
A plane graph with n¸ 3 vertices has at most
3n¡6 edges.
Read More
Use Code STAYHOME200 and get INR 200 additional OFF
Use Coupon Code

Download free EduRev App

Track your progress, build streaks, highlight & save important lessons and more!