A tree is a connected acyclic graph. The number of edges it has is one less than the number of nodes, every two nodes are connected by exactly one path and if we connect any 2 extra nodes we would have exactly one cycle. Any one of these statements will imply the others.

Cayley's formula: There are n^(n-2) possible labeled trees consisting of n nodes.

Planar graphs

Some equations that follow from any planer graph include Euler's formula: n-e+f=2 e<3n-6 Every planer graph can be colored with 5 or less

An equation describing graphs in general sum of degrees of all edges = 2e degree here means the number of edges that connect to any node.

From these equations we can prove that a graph is 5 color-able.

P(n)="Any planer graph can be colored with 6 colors or less" for n>1

Inductive Hypothesis: Assume we have a planer graph of k nodes.

Inductive step: Since this graph is planer, it has some node with degree less than or equal to 5. We can remove this node and color it some 6th color. We are left with a graph of k-1 nodes which are planer.

Conclusion: Since we can color every node in this way, we can color any graph of n nodes with 6 colors or less.

Adjacency lists

These consists of an n by n list where the list across is the list of nodes, the list down is the list of nodes, and the number at position (i,j) represents the number of edges between node i and node j (if the graph is simple this evaluates to 0 or 1).

Miscellaneous

During the second lecture we where introduced to some interesting problems and common errors that can be made when finding their solutions, one such problem involved 4 people of varying speeds crossing a bridge as follows: Four guys, Adam, Ben, Carl, and Dave, want to cross a bridge which can only hold 2 people at a time. It is pitch dark and they only have one flashlight, so they must cross either alone or in pairs (bringing the flashlight). Their walking speeds allow them to cross in 1, 2, 5, and 10 minutes, respectively; when a pair crosses, it travels at the slower speed of the two guys. Is it possible for them to cross the bridge in 17 minutes?

Although it was not initially stated, a good way to think about how to solve a problem of this nature is to represent it as a graph. We can represent this as a graph consisting of 30 nodes where each node represents a possible configuration of four people and the flashlight (on one side of the bridge verses the other). We can then draw edges between nodes that can be reached from one to the other. Each of these edges will be then be assigned a weight corresponding to the time it takes to get from one configuration to the other. We can then use Dijkstra's algorithm to find the path from the all on one side node to the all on the other side node.

Although this will guarantee a solution it is usually not the best strategy if speed is important because the problem grows exponentially larger as more nodes are added. Another bridge crossing problem can be found here here. The goal of this puzzle is to get everyone to the other side. Another puzzle that can be helped with graph theory can be found here.