A graph G is an ordered pair (V,E) where V is a set and E is a set of two element subsets of V.

```
E ⊆ { {x,y}: x,y in V, x≠y }
Typical data structure: { {A, B, C, D}, { {A,B}, {B,C}, {A,D} } }
Vertices Edges connecting nodes
```

A graph can be **directed** or **undirected**. In a **directed** graph, an edge (v1, v2) is not the same as (v2, v1) since the edge is directed from 1->2.

Graphs are the most pervasive abstraction in CS. They model networks of transportation, the world wide web, PageRank.

A graph on n vertices where every pair of vertices is connected is called an *n-clique*, denoted by Kn. Kn = (V, E) where V = {1, 2, ..., n} and E = { {i,j}: 1 ≤ i ≤ j ≤ n}. The number of edges in Kn is nC2 (number of two vertex combinations).

Two endpoints with one linear path connecting all vertices. A path on n vertices, denoted by Pn, is the graph Pn = (V, E) where V={1,2...,n} and E = { {i,i+1}: 1 ≤ i ≤ n-1 }. The total number of edges is n-1.

A path with connected endpoints. A cycle on n ≥ 3 vertices the graph Cn = (V, E) where V = {1, 2, ..., n} and E = { {i,i+1}: 1 ≤ i ≤ n-1} ∪ { {1,n}}. The number of edges in Cn is n.

Formal concept for classifying graph types. Two graphs G = (V, E) and G' = (V', E') are said to be isomorphic if there exists a bijection f: V -> V' s.t.

`{x,y} in E iff {f(x), f(y)} in E'`

The number of edges in a graph. The size of an n-vertex graph is bounded by nC2 (the n-clique).

The degree or valency of a vertex v in a graph G = (V, E) denoted by dG(v) is the number of neighbors of v in G:

`dG(v) = |{u in V: {v,u} in E}|`

A graph where every vertex has degree k is a **k-regular** and a graph is **regular** if it is k-regular for some k.

**The handshake lemma** says the number of people at a cocktail party who shake hands with an odd number of others is even. Formally, *the number of odd-degree vertices in a graph is even.*

A **distance** between two vertices in a graph is the number of edges in the shortest path (also called the graph geodesic).

epsilon(v) of vertex v is the greatest geodesic distance between v and its furthest vertex in G.

A radius r of a graph is the minimum eccentricity of any vertex.

A diameter d of a graph is the maximum eccentricity of any vertex. Algorithm to compute: find shortest path for all vertices, take the max.

- A graph G' = (V', E') is a subgraph of G iff V' is a subset of V and E' is a subset of E.
- A graph G' = (V', E') is an induced subgraph of G iff V' is a subset of V and E' = { {u,v} in E: u,v in V'}
- subset of vertices, different edges

A simple, unweighted directed graph G is an ordered pair (V,E) where V is a set and E is a set of **ordered pairs** from V.

` E is a subset of {(x,y):x,y in V, x ≠ y}`

A Directed graph does not have the notion of *degree*. Instead, *indegree* and *outdegree* of a vertex v in G, defined as |{u in V: (u,v) in E}| and |{u in V: (v,u) in E}| respectively.

Multiple edges between the same pair of vertices (this makes the collection of edges a **multiset**). A **self-loop** is an edge to and from a single vertex.

Numerical weights are associated to edges. Good for modeling physical networks.

A *tour* of G traces every edge exactly once: walk T = (v1,e1,v2,e2,...,vn,en,vn+1) s.t. ei ≠ ej for all e in T.

A tour is **Eulerian** if vn+1 = v1, V(T)=V and E(T)=E. An Eulerian tour traverses all edges and ends where it started.

A graph is **Eulerian** iff it has a Eulerian tour.

Theorem: A graph is Eulerian iff it is connected and each vertex has an even degree. (Every vertex must have an exiting edge for every entering edge)

Psudo-proof: if graph is eulerian, then every vertex must be entered and exited, therefore even number of edges. if even edges, then prove v1=vn+1 (ends where it starts) and n = |E|

Example: A network requires users that are close to have different wavelengths to prevent interference. Users can be modeled as vertices, connected by an edge if close. A *colouring* of this graph G is an assignment of colours to vertices s.t. no two adjacent vertices have the same colour.

The example is restated as, *what is the minimum number of colours needed for a colouring of G.*

A **k-colouring** of G is a function c:V->{1,2,...,k}, s.t. if {v,u} in E, then c(v) ≠ c(u). The smallest k in Naturals for which a k-colouring of G exists is called the **chromatic number** of G.

If k-colouring of G exists, the graph is **k-colourable**.

Proposition: If the degree of every vertex in a graph G is at most k, then the chromatic number of G is at most k+1.

Proof by induction on number of vertices. For one vertex, one colour is needed. Assume hypothesis. For a graph with n vertices, with chromatic number k. Add one vertex and you get chromatic number of at most k+1.

A bipartite graph can be partitioned into two parts s.t. edges of the graph only go between the two parts, but not inside a part (think domain to codomain or red-black tree).

A graph G is said to be **bipartite** iff there exists U ⊆ V s.t. `E ⊆ { {u,u'}:u in U and u' in V \ U}`

The sets U and V \ U are called the **classes** of G.

A **complete bipartite** graph Km,n is a graph with ALL possible edges between the two classes. `Km,n = (V,E) s.t V={1,2,...,m+n} and E={ {i,j}: 1 ≤ i ≤ m, m+1 ≤ j ≤ m+n}`

Another way to state the definition is a bipartite graph is 2-colourable.

Proposition: A graph is bipartite iff it contains no cycle of odd length. (cycle must end on same side)

Given a bipartite graph G=(V,E), a **matching** B in G is a set of disjoint edges.

Theorem: A bipartite graph W=(V,E) wtih classes B and G has a **perfect matching** iff |B|=|G| and