# 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:

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