Learn some graph theory--How cool it is! (plus it's already typed-so I don't ha 

Learn some graph theory--How cool it is! (plus it's already typed-so I don't ha

Graph Theory

Basic Graph Theory
Graph-a finite nonempty set V of vertices, along with a set E of edges.
A graph is often described as G(n,m) n is the number of vertices and m is the number of edges
Multigraph-contain loops, or edges connecting a vertex to itself, and/or parallel edges, several edges connecting the same pair of vertices
Simple Graphs-Have no loops or parallel edges
Degree of a Vertex- is the number of edges incident (attached) on the vertex.
Degree Theorem: The sum of the degree of the vertices is twice the number of edges.
Complete graphs-have all vertices connected by exactly one edge.
Complete Graph Theorem: For any complete graph
1. There are n(n-1)/2 edges???G(n,m)=G(n,n(n-1)/2)
2. 2. The max degree of every vertex is n-1.

Walks and Paths
Walk-the course taken from one vertex to another vertex along the edges of a graph
Trail-a walk in which no edge is used more than once
Path-a walk in which no vertex nor edge is repeated
Walks and Paths Theorem: Every walk contains a path
Circuit-a trail in which only vertices may be repeated
Cycle-No edges are repeated and only the beginning and end vertices may be the same
Connected Graph-any vertex can be reached from any other vertex
Disconnected Graph-not all vertexes can be reached from any other vertex
For G(n,m) to be connected there must be at least n-1 edges, the edges can be arranged in such a way that the graph may not be connected though.
Bridge-a bridge is an edge whose removal would cause the graph to no longer be connected

Euler Paths and Circuits
Euler Circuit-a path that includes each edge exactly once and has the same starting and ending vertex is called and Euler Circuit
Euler Path- a path that includes each edge exactly once, but has different starting and ending vertices
Euler Circuit Test: A connected multigraph contains an Euler circuit if and only if the degree of each vertex is even.
Fleury???s algorithm: finds an Euler circuit in a connected multigraph that has a large number of vertices, all of even degree
1. Choose a starting vertex and walk the edges. Mark off the edges walked as you go.
2. Do not choose a bridge unless not choosing a bridge will disconnect the circuit.
Euler Path Test: A connected multigraph has an Euler path if and only if each vertex has even degree, except for exactly two. Euler paths always start with one of the vertices of odd degree and end with the other.