The complement of a graph will have all of the same vertices but its edges will be all of the possible edges that the original graph does NOT have.

Handshaking Lemma: For any graph G, the sum of degrees of the vertices in G is twice the size of G.

Pigeonhole Principle: n pigeons in m holes, and n>m, then there must be at least one hole containing more than one pigeon.

Planar graph: a graph without any edges crossing each other

For graph, G, to be planar:

If G is a simple graph:

If G is a bipartite graph:

Any subgraph that contains K5 or K3,3 will not be planar

A connected graph has an Eulerian circuit if and only if ALL of its vertices are even.

A connected graph is semi- Eulerian if and only if it has exactly two vertices of odd degree. (roads)

Hamiltonian Graph is a connected graph G that has a cycle which included every vertex. (towns)

The number of different Hamiltonian cycles in a complete undirected graph on n vertices is (n-1)!/2 and in a complete directed graph on n vertices is (n-1)!

Find minimum spanning tree

Practice: 2008 Nov. Paper 3 Question #2

Kruskal’s method:

- Select an edge with the smallest weight.
- Select from the remaining edges, the edge of least weight which does not form a cycle.
- Repeat step 2 until n-1 edges have been chosen

Prim’s method:

- Select any vertex as a starting point.
- Consider the edges that connect to any vertex already chosen and choose the smallest .
- Repeat step 2 until all of the vertices have been chosen.

Prim’s method (matrix): SAME THING!!!

Dijkstra’s method: Find the shortest path from a start point to a finish point.

- Label the starting vertex with a (0,p) where ‘p’ means permanent. Label all other vertices with where ‘t‘ means temporary.
- Choose the least of all temporary labels adjacent to any permanent vertex. Then make it permanent.
- Repeat step 2 until the destination vertex has a permanent label.

Chinese postman (roads)

- Find the shortest route between the 2 odd vertices.
- Add all of the edges and then add the shortest route between the odd vertices (count this twice)

When there are more than 2 odd vertices: pair up odd vertices and find the smallest.

Practice: 2010 May Paper 3 Question #2

Traveling salesman (towns)

Lower bound:

- Select any vertex, X, and find the sum of the 2 smallest weights that touch X.
- Remove vertex X, with its edges, from the graph and find the minimum spanning tree for this new network.
- Add the totals in steps 1 &2.

Upper bound:

Double the weight of the minimum spanning tree.

A better upper bound would be to just head straight back to starting point.