A graph is comprised of vertices (sometimes called nodes) and edges.  Vertices are considered distinct and unique, and the edges between vertices define the actual graph.  Below are examples of planar graphs.  (The solid circles are vertices; the lines between vertices are the edges.)  There are many ways to represent graphs, and there are many problems that can be solved using graphs.  Vertices can be colored to represent unique elements, edges can have color and direction, and graphs can be tested for a number of unique properties.  A graph can be used to describe a map of countries, the connectivity of an electrical circuit, chemical structure, a system of highways, and even a simple game of blocks.

Example 1

Example 2

Example 3

Example 4

There are several properties of study within Graph Theory.  First, planarity is defined as whether vertices can be arranged in such a way that no edges cross.  Once a graph can be drawn planar, the following equation can be used.

Where v is the number of vertices, e is the number of edges, r is the number of enclosed regions (the infinite space outside the graph counts once).  The first two examples have three regions, seven vertices, eight edges.  7 - 8 + 3 = 2.  It is no coincidence that these two examples have so many similarities; they are actually the same graph.  Another property of graphs is isomorphism.  Two graphs are said to be isomorphic if a one-to-one relationship can be defined that correlates each vertex and edge to both graphs.  Such a correlation can be used to prove that two graphs are essentially the same, even if they may not appear the same.

How is this useful? Suppose a chemical compound was described using vertices for atoms and edges as chemical bonds.  Graph isomorphism could be used to compare very complex chemical compounds for equality.  Rather than solving the same problem twice, one can simply check for isomorphism and apply the solution to two unique situations.

Another property of Graph Theory is whether a graph is bipartite. Suppose each vertex was a country on a map, each edge was a border between two countries, and we wanted to draw the map with as few colors as possible.  If we can color the map with only two colors, then the given graph is bipartite. 

Bipartite graphs can be arranged to appear like the following:

Graph Theory is a vast field of study when studied in conjunction with Discrete Mathematics.  For example, it is no trivial matter to count the number of distinct paths in Example 4 above, or in the bipartite graph above. 

• Let a path be defined as a way to traverse the graph from a source point to a destination point without repeating vertices or edges.
• Let a walk be defined as a way to traverse the graph from a source point to a destination point where vertices and edges can repeat.
• Let a trail be defined as a way to traverse the graph from a source point to a destination point where vertices can repeat and edges cannot repeat.
• Let a circuit be a closed loop where no edges can repeat, but vertices can repeat.
• Let a cycle be a closed path (source and destination are the same), where vertices and edges cannot repeat.
• Let a vertex's degree be the number of edges touching it.
• Let Kn be the complete graph on n-vertices.  The complete graph contains all possible edges between all vertices.  Note that all Kn graphs above n > 5 are NOT planar.
• Let the complement graph contain the same vertex set but contains the edges that are not in graph but are in the complete graph.
• Let the null graph contain no edges.
• Let the formal definition of graph isomorphism be that a functoin that is one-to-one and onto exist from the vertex set of the first graph to the vertex set of the second graph be such that the edge set for all edges in the first graph f: {a,b} -> {f(a), f(b)
• Let K-regular mean that all vertices have the same degree.
• An Euler circuit is defined as a closed loop where all edges are visited exactly once.  Vertices may repeat.
• An Euler trail is an open trail where all edges are visited once.  Vertices may repeat.
• Let the dual graph have vertices where there are regions, and let the edges be the boundaries of the previous graph.
• Let Qn be the hypercube of n-dimensions.
• The Hamilton cycle is a closed cycle where every vertex is visited exactly once.
• The Hamilton path is a path where every vertex is visited exactly once.
• Let the chromatic polynomial be the mathematical description of the number of colors needed to color the graph.
• Let the chromatic number be the minimum number of colors needed to color a graph.
• Let a color critical graph be where removing any vertex lowers the chromatic number by 1.
• Let a tournament be a directed complete Kn graph with no loops.

As you can see, Graph theory is a rather involved field with many definitions.  These definitions extend even further into computer science when a graph is a tree. 

A tree is a graph without any cycles (loops). If no closed loops exist, then the number of regions is equal to 1.  All trees are planar.  Substituting this value into the planar equation gives:

This can be simplified to:

This special property is true for all trees.  It can be proved rather easily by induction. Now, to add to the many definitions, below are a few special properties of trees:

• Let the root be the main starting point of a tree.  This is commonly represented as the top node.
• Let the children of the root be vertices directly connected to the root.
• Let a branch be a group of nodes connected to the root.
• Let the leaves be end points of branches.
• Let the height be the depth away from the root. The root is considered at a height of zero.
• Let a full tree be a tree where every leaf has the same height.
• Let a complete tree be a tree where every node has 0 or m children, for an m-ary tree.
• Let a balanced tree be a tree where every leaf is of height h or h-1

It has been said that Graph Theory has more definitions than any other field of mathematics.  This is almost certainly true!  Unfortunately all this information only scratches the surface of Graph Theory!

• Journal of Graph Theory - has some nice Peterson graphs as a logo
• Graph Theory Tutorials - some excellent topics of study
• Graph Theory Lessons - some great miscellaneous info
• The Four Color Theorem - the map maker's problem