# Graph Theory

Graph a pair $G = (V, E)$. $V$ a set of vertices $E$ a set of pairs of vertices called the edges* of the graph.

## Example

Below is a graph

$V = \{a,b,c,d\}$ $E = \{\{a,b\}\},\{a,c\},\{b,c\},\{b,d\}\}$

.. figure:: |filename|/math240res/images/graphexample1.png

A graph can also have nodes that are not connected with edges

$V = \{a,b,c,d\}$ $E = \{\{a,c\}\}$

.. figure:: |filename|/math240res/images/graphexample2.png

# Example of a problem that can be solved using graph theory

## Claim

In any group of 104 people, there will be an even number of people with odd number of friends.

## Proof

First generalize the statement: For any integer $\geq 1$, in any group of n people, there are even number of people with an odd number of friends.

We usually write $n=|V|$, $m = |E|$

Let’s prove the generalized statement using induction on $m$.

Base case ~~~ $m=0$, $\sigma =$ number of people with an odd number of friends $= 0$

Induction Step ~ Let $G=(E,V)$

originally, $\sigma$ is odd.

This is how G looks like

.. figure:: |filename|/math240res/images/graphexample3.png

Removing any edge e, this gives $G\backslash\{e\}$.

.. figure:: |filename|/math240res/images/graphexample4.png

In $G\backslash\{e\}$, $\sigma$ is even. What happens when we add back in edge $e = \{u,v\}$ ?

There are 3 possibilites:

1. u, v are both even number of friends in $G\backslash\{e\}, \sigma \leftarrow \sigma +2$
2. e, v are both odd in $G\backslash\{e\}, \sigma \leftarrow \sigma -2$
3. Exactly one of u, v is even in $G\backslash\{e\}, \sigma \leftarrow \sigma$