Combinatorics • Topic 26

Graph Theory Basics

Graph theory models pairwise relations between objects. It is the study of vertices (dots) and edges (lines connecting dots).

Definitions

Definition (Graph)

A graph

G = (V, E)

consists of:

Order: $∣ V ∣$ , the number of vertices.
Size: $∣ E ∣$ , the number of edges.
Simple Graph: No loops (edge to self) and no multiple edges between the same pair.

Complete Graph ( $K_{n}$ ): Every pair of vertices is connected. $∣ E ∣ = (2 n)$ .
Path Graph ( $P_{n}$ ): Vertices connected in a line.
Cycle Graph ( $C_{n}$ ): Vertices connected in a closed loop.
Bipartite Graph: Vertices can be split into two sets $A, B$ such that all edges go between $A$ and $B$ .

Theorem (Handshaking Lemma)

The sum of the degrees of all vertices is twice the number of edges.

v \in V \sum de g (v) = 2∣ E ∣

Corollary: The number of vertices with odd degree must be even.

Exercise (Problem 1)

There are 15 people at a party. Is it possible for each person to shake hands with exactly 3 others?

Exercise (Problem 2)

Draw all non-isomorphic graphs with 4 vertices.

Exercise (Problem 3)

Prove that in any group of 6 people, there are either 3 mutual friends or 3 mutual strangers (Ramsey Theory intro).