From Privateer

Contents 1 Graphs 2 What is a graph? 2.1 Basic Definitions and Terminology 2.1.1 Degree 2.1.2 Simple Graph 2.1.3 Loops & Multiedges 2.2 Examples 2.2.1 Peterson Graph 2.2.2 Complete Graph 2.2.3 Regular Graphs 2.2.4 Hyper Cubes 2.3 Directed Graphs 3 Ways to Represent a Graph 3.1 Edge and Vertex List 3.2 Edge List 3.3 Adjacency Matrix 3.4 Incidence Matrix 4 Graph Isomorphisms and Automorphisms 5 Bipartitions and N-partitions 5.1 Examples 6 Walking Graphs 6.1 Paths 6.2 Königsberg Bridge Problem 6.2.1 Eulerean Circuits 7 Subgraphs 8 Vertex Deleted Subgraphs 9 Degree Sequences 9.1 Havel-Hakimi Algorithm

Graphs

What is a graph?

A graph is a set of verticies, edges, and an incidence relation that associates edges with verticies. A graph is often denoted ${\displaystyle G}$. The vertex set of ${\displaystyle G}$ is then ${\displaystyle V\left(G\right)}$, the set of edges of ${\displaystyle G}$ is ${\displaystyle E\left(G\right)}$.

This definition is all that constitutes a graph. See the House Graph for a simple example.

Generally, graphs are finite (that is, they have a finite number of edges and verticies), though there are some exceptions.

Basic Definitions and Terminology

Degree

The degree of a vertex is the number of edges incident with it. If there are 3 edges connected to a vertex, it has degree 3. ${\displaystyle \delta \left(G\right)}$ represents the minimum degree of any vertex in a graph ${\displaystyle G}$. ${\displaystyle \Delta \left(G\right)}$ represents the maximum degree of any vertex in a graph. The maximum degree of the house graph is 3, the minimum degree is 2.

Simple Graph

A simple graph is a graph with no loops or multiedges.

• Loop: A loop is an edge with the same vertex at both end points.
• Multiedge: more than one edge between two verticies.

Loops & Multiedges

Examples

Peterson Graph

The Peterson graph is the simple graph whose verticies are the 2-element subsets of a 5-element set, and whose edges are the pairs of disjoint 2-element subsets.

See: Peterson Graph

Complete Graph

The complete graph, denoted ${\displaystyle K_n}$, is the graph with ${\displaystyle n}$ verticies, where each vertex is adjacent to every other vertex. Thus the degree of all verticies in ${\displaystyle K_n}$ is equal to ${\displaystyle n-1}$.

See: K2, K2, K3, K4, K5, K6, K7, K8

Regular Graphs

A regular graph is a graph in which the degree of every vertex is equal. All of the hypercubes are regular graphs, as are the complete graphs.

Hyper Cubes

Examples: Q0, Q1, Q2, Q3, Q4, Q5

Directed Graphs

A directed graph is a graph with directions applied to the edges. The directions can be thought of as a road map with "one way" streets.

Ways to Represent a Graph

As you have seen from the examples above, the most common way to represent a graph is by drawing it out. Dots represent verticies, lines between the dots represent edges. Here are some other ways to represent graphs:

Edge and Vertex List

An Edge and Vertex list is a list of all of the verticies and edges in a graph, and their incidence relation.

The house graph might be represented like this:

${\displaystyle V=\{v_1,v_2,v_3,v_4,v_5\}}$

${\displaystyle E=\{e_1,e_2,e_3,e_4,e_5\}}$

$$ I :	$$ e 1 = { v 1 , v 2 }
	$$ e 2 = { v 5 , v 2 }
	$$ e 3 = { v 5 , v 1 }
	$$ e 4 = { v 2 , v 3 }
	$$ e 5 = { v 5 , v 4 }
	$$ e 6 = { v 4 , v 3 }

Edge List

Because the edges in graphs are always connected by at least two verticies, it is possible to simplify the above by just writing an edge list.

The edge list of the house graph: ${\displaystyle e_1=\{v1,v2\},e_2=\{v5,v2\},e_3=\{v5,v1\},e_4=\{v2,v3\},e_5=\{v5,v4\},e_6=\{v4,v3\}}$

As you can see, this edge list encodes all of the edges and all of the verticies, including which verticies are incident with each other.

Adjacency Matrix

An adjacency matrix is a special binary valued matrix that shows which verticies are incident with each other in a simple graph. The rows and columns are the verticies of the graph listed in the same order. The cells of the matrix are 1 of there is an edge between the two verticies or 0 if there is no edge between the two verticies. The diagonal of the matrix will always be zero. The adjacency matrix is also a symmetric matrix.

The adjacency matrix of the house graph:

	$$ v 1	$$ v 2	$$ v 3	$$ v 4	$$ v 5
$$ v 1	0	1	0	0	1
$$ v 2	1	0	1	0	1
$$ v 3	0	1	0	1	0
$$ v 4	0	0	1	0	1
$$ v 5	1	1	0	1	0

Incidence Matrix

Incidence Matrix

Graph Isomorphisms and Automorphisms

Bipartitions and N-partitions

Examples

Complete bipartite graphs: K12, K23, K13, K34

Walking Graphs

Paths

Königsberg Bridge Problem

Euler wondered, whilst wondering about Königsberg, whether it was possible to see the entire city without crossing the same bridge twice. In other words, is it possible to cross all of the bridges in the city exactly once and end up where you started?

Königsberg had seven bridges, crossing the Pregel river. This question translates nicely into a problem of Graph Theory.

Image:Königsberg Bridge Illustration.png

By numbering the bridges and the banks of the river, you can create the following graph:

Image:Königsberg Bridge Graph.png

Try it yourself. Pick a starting vertex, say ${\displaystyle y}$, and attempt to find a path that takes you along each edge and returns you to ${\displaystyle y}$. You should find it a pretty difficult task. Actually, it turns out that it is impossible to do on this graph.

Eulerean Circuits

Subgraphs

a graph ${\displaystyle H}$ is a subgraph of a graph ${\displaystyle G}$ if:

1) the vertex set of ${\displaystyle H}$ is a subset of the vertex set of ${\displaystyle G}$; ${\displaystyle V\left(H\right)\subseteq V\left(G\right)}$, and

2) the edge set of ${\displaystyle H}$ is a subset of the edge set of ${\displaystyle G}$; ${\displaystyle E\left(H\right)\subseteq E\left(G\right)}$

For example, ${\displaystyle P_5\subseteq C_5}$:

Vertex Deleted Subgraphs

A vertex deleted subgraph is a subgraph of a graph with a vertex removed.

This is the complete set of single vertex deleted subgraphs of the House Graph.

You might ask yourself whether, given a complete set of vertex deleted graphs for some graph ${\displaystyle G}$, if you could figure out what the original graph was. Some properties of the origignal graph jump out. For example, the size of the set of vertex deleted subgraphs is equal to the number of verticies in the original graph. It seems reasonable that given the entire set of vertex deleted subgraphs that you could recreate the entire graph. And, in many cases this is possible. However, there is no proof for any graph, and this is an open problem called the reconstruction conjecture.

Degree Sequences

Havel-Hakimi Algorithm