Graph Theory

Proposition: (G) is a (connected) graph, (G) is Eulerian if and only if all vertices degrees are even

Proof: “(\rightarrow)“ Last class.

((\leftarrow)) Suppose all vertex degrees in (G) are even and (G) connected.

Idea: Start from any circuit, build longer circuits, end up with Eulerian circuit.

Lemma: If $ C = w_1, w_2, \dots, w_k = w_1$ is a circuit, and (C^\prime = w_i, x_1, x_2, \dots ,x_j,w_i) is a second circuit, then

$ \hat{C} = w_1, w_2,\dots, w_i, x_1, x_2, \x_j, w_i, w_{i+1}, \dots w_k$

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

So let (C = ebdfe) be any circuit in (G) that has no repeated edges

If (C) is Eulerian then (G) is Eulerian If (C) is not Eulerian, then since (G) is conneted there is some (v) in (V) (say (v=d)) that touches an edge not in (C). Ignoring (C), still an even number of edges touching every vertex. Let (C^\prime = dcgfed) be a circuit starting and ending at (V), using none of the same edges as (C) and using no edge twice.

We make $\hat C = ebdcgfedfe $.

Keep adding circuits using the lemma until we have an Eulerian circuit. This is not just a proof, but an efficient algorithm for finding Eulerian circuit.

Note: Messy here eh? I find it messy too, but I hardly find any other better way to explain it.

Hamiltonian Paths and Cycles

Definition

A Hamiltonian cycle in a graph (G=(V,E)) is a cycle (w_1,w_2,\dots,w_n,w_1) that passes through every vertex in (G).

It is NP-complete to determine whether a graph has a Hamiltonian Cycle.

Example: Petersen graph

.. image:: http://upload.wikimedia.org/wikipedia/commons/thumb/9/91/Petersen1\_tiny.svg/200px-Petersen1\_tiny.svg.png

2 edges incident to each vertex must be used.

Some edge of inner star must be used, 2 edges between inner star, outer cycle must be used.

It’s impossible to get Hamiltonian Cylcle from Petersen graph.

Why:

Label the corresponding vertices on the pentagon and star by 0, 1, 2, 3, 4.

If a Hamiltonian cycle exists it must cross the bridge (between inner and outer loops) an even number of times, i.e. 2 or 4 times. Hence it must travel along the inner & outer loops 8 or 6 times.

Case 1: 8 times. The cycle must travel along the inner loop & outer loop 4 times each. It is easy to verify such a loop does not exist.

Case 2: 6 times. The cycle cannot travel on the outside/inside loop 5 times. So we must have 3 on the inside & 3 on the outside. Suppose we have 0-1-2 on the outer loop. Then bridge 1 is not used. So the remaining 4 bridges 0, 2, 3, 4 must be used. And the inner 1 is not adjacent to the outer 1, so we must have 4-1-3 on the inner loop. Having found 8 out of the 10 edges of the cycle, it is easy to verify that such a cycle does not exist.

Theorem (Dirac)

(G(V,E)) with (n) vertices, (G) is Hamiltonian if (n\geq3) and each vertex has degree $\geq{ n \over 2} $

Handshaking Lemma

The first graph theory problem

$G=(V,E)$

In any graph, there are an even number of points (vertices) that touch an odd number of lines (edges).

Definition

Given a graph $G=(V,E)$ and $v\in V$, the degree of $v$ is the number of edges that contain $v$, and is denoted $d(v)$ or $d_G(v)$

For example

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

Lemma: Handshaking Lemma

For any graph $G=(V,E)$.

\[ \sum_{v \in V} d(v) = 2|E| \]

This immediately implies the fact from last class.

Proof: Each edge is counted twice in total, once by each of its endpoints.

Walk

A walk in a graph $G=(V,E)$ is just a sequence of vertices, $w_1,w_2,\dots,w_{k-1},w_k$ such that $\{w_1,w_2\} \in E$, $\{w_2,w_3\} \in E$, … $\{w_{k-1},w_k\} \in E$

Example: ababcecd is a walk

A walk is a path if it has no repeated vertices. A graph $G=(V,E)$ is connected if for any $u,v \in V$, there is a walk starting at u, ending at v.

Fact

if there is a walk from u to v then there is a path from u to v.

Proof

Let $u=w_1,w_2,\dots,w_k=v$ be a walk from u to v of minimum length. If $w_1,w_2,\dots,w_k$ is not a path, then there is some $i<j$, such that $w_i=w_j$, and then $w_1,w_2,\dots,w_i,w_j,\dots,w_k$ is a shorter walk, then $w_1,w_2,\dots,w_k$ is a path.

Circuit, Cycle and Eulerian

A circuit is a walk $w_1,w_2,\dots,w_k$ sucht that $w_k = w_1$. The circuit is a cycle if $w_1,w_2,\dots, w_k-1$ is a path.

An Eulerian walk in $G=(V,E)$ is a walk that uses each edge exactly once. An eulerian circuit is a circuit that uses each edge exactly once.

A graph is Eulerian if it has an Eulerian circuit.

Theorem (Euler, 1736)

If $G$ is a (connected) graph, then it is Eulerian if and only if all vertex degrees are even.

Proof

“$\rightarrow$” Suppose $G$ has an Eulerian circuit $w_1,w_2,\dots,w_k$, Fix any vertex $v \in V$. Then $v$ appears at some points in the walk, say $w_{i_1},w_{i_2},\dots, w_{i_j}$.

If $i_1 \not = 1$: Then the edges of $G$ incident to $c$ are

\[ \left\{ w_{i_1-1},v \right\}, \left\{ v,w_{i_1+1} \right\}, \left\{ w_{i_2-1},v \right\}, \left\{ v,w_{i_2+1} \right\},\dots, \left\{ w_{i_j-1},v \right\} , \left\{ v,w_{i_j+1} \right\} \]

So $d_G(v) =2_j$

If $i_1 = 1$: Then $d_G(v)=2(j-2)+1+1 = 2(j-1)$

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 $

Recurrence Relation

Fibonacci numbers

Fibonacci numbers are defined as:

(F_0 = 0, F_1 = 1), for (n\geq 1), $F_{n+1} = F_n +F_{n-1} $

How to solve recurrence relation in general

In general, consider a recurrence equation of the form (X_{n+1} + \beta X_n + \gamma X_{n-1} = 0) where (n\geq 0).

Let (X_0 = c_0) and (X_1=c_1)

We consider it as a quadratic equation and solve for (x^2 + \beta x + \gamma = 0).

\[ x^+ = \left ( {- \beta + \sqrt {\beta^2-4\gamma} }\over{2} \right) \]

\[ x^- = \left ( {- \beta - \sqrt {\beta^2-4\gamma} }\over{2} \right) \]

If $x^+ \neq x^- $ then solution is \[X_n = A(x⁺⁾n + A^\prime (x^-)n \] where \[A+A^\prime = c_0 \] \[Ax^+ + A^\prime x^- = c_1 \]

Note: The these big X’s and small x’s used here very visually confusing, but sadly that’s how the instructor wrote it and I didn’t want to change anything.

Consider the example of Fibonacci sequence

\[ F_{n+1} - F_n - F_{n-1} = 0 \]

here we have (\beta = -1) and (\gamma = -1)

Solve for (x^2-x-1), We get

\[ x^+ = {1+\sqrt{1+4}\}\over {2} \] \[ x^- = {1-\sqrt{1+4}\}\over {2} \]

So we have (x^+ \neq x^-)

\[ F_n = A \left( {1+\sqrt{5}\} \over {2} \right)^n + A^\prime \left( {1-\sqrt{5}\}\over {2} \right)^n \]

where (A+A^\prime = 0) and (Ax^+ + A^\prime x^- = 1)

Solve for (A) and (A^\prime) we get

\[ F_n = {\{1}\over{\sqrt 5}\} \left( {1+\sqrt{5}\} \over {2} \right)^n -{\{1}\over{\sqrt 5}\} \left( {1-\sqrt{5}\}\over {2} \right)^n \]

RSA encryption

RSA encryption is not vulnerable to man in the middle attack. Let’s discover why.

Public Key

A piece of info I published by an entity, allowing others to securely send messages to that entity. The info, I should allow others to send me securely encrypted messages that only I can quickly decrypt

RSA Encryption Practice

Based on hardness of factorization. (This is not the same as primality testing)

My private info: Two large primes $q_1$ and $q_2$

My public key $I$:

1. A large prime p
2. The product n

Where $ I = (P,n) $ and $ n = q_1 \cdot q_2 $

Aside: $p$, $q_1-1$, $q_2-1$ needs to be all relatively prime, this happen by chance

Now Bob wants to send me a message M (think of M as a number of less than 500 digits). To encrypt, he calculates $\hat M = M^p \pmod n$, then sends it. To decrypt, I want to rise $\hat M$ to some power d, need to find d such that $\hat M^d \pmod n =M$

Step 1

Solve $a\cdot (q_1 -1)\cdot(q_2 -1 ) \equiv -1 \pmod p$. This can be done by using Euclid’s algorithm to find a, b such that $a\cdot (q_1 -1)\cdot (q_2 -1 ) = b \cdot p -1$

Step 2

Compute $\hat M^b \pmod n = M^{p\cdot b} \pmod n$

Claim: $M^{p \cdot b} \pmod {n} = M $

Proof: \[ \begin{aligned} M^{b\cdot p}\pmod{q_1} & = M^{a(q_1-1)(q_2-1)+1} \pmod {q_1} \\ & = [M^{q_1-1}]^{a(q_2-1)} \14\pmod {q_1} \\ by \ FLT & = M \pmod{q_1} \\ &=M \end{aligned} \] Similarily \[ \begin{aligned} M^{b\cdot p}\pmod{q_2} & = M^{a(q_1-1)(q_2-1)+1} \pmod {q_2} \\ & = M \end{aligned} \]

Then:

$q_1 \mid (M^{b\cdot p} -M)$ and $q_2 \mid (M^{b\cdot p} -M)$. Since $q_1$, $q_2$ are primes, we get $q_1 \cdot q_2 = n \mid (M^{b\cdot p} -M)$

$\therefore M^{b\cdot p} \pmod{n} = M$