Courses

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. Use Code STAYHOME200 and get INR 200 additional OFF Use Coupon Code