Graph Theory

A graph (more generally called an undirected graph) is a set s V  and a subset E of V×V (.  We tend to think of V as a set of points (the vertices) and E as a set of edges/line segments.  So one graph might look like this:

Graph[ {1\[UndirectedEdge]2, 2\[UndirectedEdge]3, 3\[UndirectedEdge]1, 3\[UndirectedEdge]4, 3\[UndirectedEdge]5,5\[UndirectedEdge]6, 6\[UndirectedEdge]1, 7\[UndirectedEdge]8,8\[UndirectedEdge]9,9\[UndirectedEdge]7, 9\[UndirectedEdge]10}, VertexLabels->Thread[ Range[10]-> Range[10]]]

A multigraph is a version of a graph where you allow multiple edges to connect the same set of points, and a directed graph (or digraph) is one where the edges have an implied direction to them (so A can be connected to B without B being connected to A):

Graph[ {1\[UndirectedEdge]2, 1\[UndirectedEdge]2, 1\[UndirectedEdge]2,2\[UndirectedEdge]3}, PlotLabel-> "Multigraph"]

Graph[ {1\[DirectedEdge]2, 2\[DirectedEdge]1,2\[DirectedEdge]3, 3\[DirectedEdge]1}, PlotLabel-> "Directed graph"]

You are most likely to see “standard” graphs rather than multigraphs or digraphs on the exam.  

If G is a graph, a (vertex-induced) subgraph of G is a subset S of the vertices of G together with those edges from G which connect points in S.

In a graph the degree of a vertex is how many edges go to it. 

A graph is called connected if you can get from any vertex to any other vertex using the edges.  Every graph can be broken up into “connected components” (each of which is a connected  subgraph on its own - the first example of a graph has two connected components).

A graph is called complete if every vertex is connected to every other vertex.  The complete graph with n vertices is given the notation (Subscript[K, n]).

 A graph is called bipartite if its vertices can be divided into two subsets A and B such that all the graph edges are between vertices in A and B (and no no edges run between vertices in A and none run between vertices in B).

Graph[ {1\[UndirectedEdge]4,1\[UndirectedEdge]5,1\[UndirectedEdge]6,1\[UndirectedEdge]7,2\[UndirectedEdge]4,2\[UndirectedEdge]5,2\[UndirectedEdge]6,2\[UndirectedEdge]7, 3\[UndirectedEdge]4,3\[UndirectedEdge]7}, VertexLabels-> Thread[ Range[7]-> Range[7]], VertexSize->Thread[ Range[7]-> {Large, Large, Large, Medium, Medium, Medium, Medium}], PlotLabel-> "A bipartite graph with A={1,2,3}, B={4,5,6,7}"]

The complete bipartite graph (Subscript[K, m,n])is the bipartite graph with a set A of m vertices, a set Bof n vertices, and every edge between A and B being included in the graph.

A graph is called planar if the vertices can be placed in the plane in such a way that no two edges cross except at their endpoints.  If v is the number of vertices, e the number of edges, and f the number of faces/regions (including the outside) in a connected planar graph, then v-e+f=2. 

If G is a graph with n vertices, the adjacency matrix for G is the matrix whose i-(j^th) entry is 1 if vertex iis connected to vertex j and 0 otherwise (this can be defined for directed graphs in the same way, and for multigraphs as the i-(j^th) entry is the number of edges connecting vertex i to vertex j).  The incidence matrix for a graph must be symmetric.  If A is the adjacency matrix of E, then (A^k) is the matrix whose i-(j^th) entry is the number of walks from vertex i to vertex j that consists of exactly k steps/edges.

If G is a graph, an Euler circuit (sometimes called an Euler tour or cycle) is a loop you walk through the vertices (possibly visiting a vertex more than once) that uses each edge exactly once.  A graph has an Euler circuit if and only if all vertices with degree greater than 0 are in a single connected component and all vertices have even degree.  An Euler path is walk (not necessarily a loop) that uses each edge exactly once (such a path is possible only if the graph is connected and if either all vertex degrees are even or exactly two are odd).  The "Seven Bridges of Köningsberg" problem was solved by converting  into the existence of an Euler walk in a particular graph.

If G is a graph, a Hamiltonian circuit/tour/cycle is a loop that visits each vertex exactly once.  A Hamiltonian path is a path that visits each vertex exactly once (without necessarily being a loop).

If G is a planar graph with vertices {(Subscript[v, 1]),....,(Subscript[v, n])} and faces/regions {(Subscript[f, 1]),...,(Subscript[f, k])}, the dual graph (SuperStar[G]) is a graph with vertices {(Subscript[f, 1]),...,(Subscript[f, k])} and two "vertices" being connected if and only if the corresponding faces in G are bounded by a common edge.