Math 240 Discrete Mathematics - Graph Theory

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 $