Graph Theory Basics

First called geometry of position by Leibnitz, graph theory grew out geometry where relations are dependent on just the position of objects. Leonhard Euler than formalized and began investigating his branch of mathematics more thoroughly (Euler, 2006). More history can be found on the History and Background Page. Today graph theory is a thriving realm of study for mathematicians and ammeters that enjoy studying puzzles. In grade school, graph theory has not often been taught, but is now so widely used today that it is important topic. This is why now it is included in the 8th grade honors Utah Core Standards. This website explains the notations, history, underlying mathematics, and applications of graph theory today.

Notation:

Below are a list of definitions and the notation that will be used throughout this website (there are many discrepancies in notation 
throughout literature on graph theory):
	A graph is made up a set of edges and vertices or G = (V, E):
		V = {v1,v2,v3,...,vn )
		E = {v1 v2,v1 v3,...,v(n-1) vn }  and e ∈ E ∋ e = {v,w}  and v,w ∈ V 
	A graph H is a subgraph of another graph G if and only if V(H) ⊆ V(G) and E(H) ⊆ E(G).
	Two vertices are adjacent if they are connected by one edge.
	A complete graph on n vertices occurs when all of the n vertices are adjacent, denoted Kn.
		 If K3  then V={v1,v2,v3 }  and E={v1 v2,v2 v3,v3 v1}={e1,e2,e3} 
	The number of edges that are incident with a vertex v is the degree of that vertex.
		 K3  the degree of v1  is 2,or deg v = 2 
	A walk is a sequence of alternating vertices and edges in which each edge is incident to the vertex preceding it. It is closed if
	the starting vertex is the same as the ending, otherwise it is open.
		 A walk for K3  is v1, e1, v2, e2, v3 
	A trail is a walk where all the edges are distinct. 
		
	A path is a walk where all the vertices are distinct.
			
	A circuit is a closed trial.
	A graph is connected if and only if there exists a walk between any two of the vertices in the graph.
	
 (Goodaire & Parmenter, 2006)
 (Walks: paths, cycles, trails, and circuits, 2000)

BACK TO THE TOP