Graph theory

This kind of graph is not a plotted curve. It is a picture of links. The vertices can be people, cities or computers. An edge joins two of them when they are linked, for example as friends or by a road.

The degree of a vertex is the number of edges that touch it. The first result to learn is the handshake lemma. Add up the degrees of all the vertices. The total is exactly twice the number of edges, because each edge has two ends.

A small example

At a party of 5 people, can each person shake hands with exactly 3 others?

• Make each person a vertex and each handshake an edge.
• Each vertex would have degree 3. The degrees would add up to 5 × 3 = 15.
• But the total must be twice the number of edges, so it must be even.
• 15 is odd. So this is impossible.

With 4 people it works. Everyone shakes hands with everyone else. The degrees add up to 4 × 3 = 12, so there are 6 handshakes. Notice that the proof never drew the graph. An odd-or-even count was enough.

Where it fits

This goes beyond the Class 10 board syllabus. HBCSE's syllabus for the Mathematical Olympiad names it under combinatorics, as elementary graph theory. The Mathematics Teachers' Association (India), MTA(I), conducts IOQM, the first stage of the Mathematical Olympiad Programme that HBCSE organises for NBHM.

About the author

Mohit Sardana

Chief Architect

An engineer (B.Tech, Computer Science) with over 20 years of preparing students for entrance exams, including as Dean at FIITJEE and Vice-President at Aakash. He is the chief architect of the TRUpreBoards evaluation engine.

Mohit Sardana on LinkedIn