Graph Theory/Definitions

Graph, node and edge

A simple undirected graph with three vertices and three edges. Each vertex has degree two, so this is also a regular graph.

A graph is an ordered pair $G=(V,E)$ where,

• V is the vertex set whose elements are the vertices, or nodes of the graph. This set is often denoted $V(G)$ or just $V$.
• E is the edge set whose elements are the edges, or connections between vertices, of the graph. This set is often denoted $E(G)$ or just $E$. If the graph is undirected, individual edges are unordered pairs $\left\{u,v\right\}$ where $u$ and $v$ are vertices in $V$. If the graph is directed, edges are ordered pairs $(u,v)$.

Two graphs $G$ and $H$ are considered equal when $V(G)=V(H)$ and $E(G)=E(H)$.

The order of a graph is the number of vertices in it, usually denoted $|V|$ or $|G|$ or sometimes $n$. The size of a graph is the number of edges in it, denoted $|E|$ or $\Vert G\Vert$, or sometimes $m$. If $n=0$ and $m=0$, the graph is called empty or null. If $n=1$ and $m=0$, the graph is considered trivial. If $1\leq n$ and $m=0$, the graph is called discrete.

Undirected graph

An undirected graph is one in which edges have no orientation. The edge (a, b) is identical to the edge (b, a), i.e., they are not ordered pairs, but sets {u, v} (or 2-multisets) of vertices.

Directed graph

A directed graph

A directed graph or digraph is an ordered pair D = (V, A) with

• V a set whose elements are called vertices or nodes, and
• A a set of ordered pairs of vertices, called arcs, directed edges, or arrows.

An arc a = (x, y) is considered to be directed from x to y; y is called the head and x is called the tail of the arc; y is said to be a direct successor of x, and x is said to be a direct predecessor of y. If a path leads from x to y, then y is said to be a successor of x and reachable from x, and x is said to be a predecessor of y. The arc (y, x) is called the arc (x, y) inverted.

A directed graph D is called symmetric if, for every arc in D, the corresponding inverted arc also belongs to D. A symmetric loop-less directed graph D = (V, A) is equivalent to a simple undirected graph G = (V, E), where the pairs of inverse arcs in A correspond 1-to-1 with the edges in E; thus the edges in G number |E| = |A|/2, or half the number of arcs in D.

A variation on this definition is the oriented graph, in which not more than one of (x, y) and (y, x) may be arcs.

Example

A drawing of a labelled graph on 6 vertices and 7 edges.

In the image you can see a graph.

The set of the vertices of the graph is $V(G)=\left\{1,2,3,4,5,6\right\}$.

The set of edges of the graph is $E(G)=\left\{\left\{1,2\right\},\left\{1,5\right\},\left\{2,3\right\},\left\{2,5\right\},\left\{3,4\right\},\left\{4,5\right\},\left\{4,6\right\}\right\}$.

The order of this graph is $|V(G)|=6$.

The size of this graph is $|E(G)|=7$.

Subgraphs, contractions, and graph minors

Subgraphs

Given a graph $G=(V,E)$ and a graph $G'=(V',E')$, $G'$ is a subgraph of $G$ if and only if $V'\subseteq V$ and $E'\subseteq E$. A clear result of this is that the every graph $G$ has as subgraphs at least the empty graph and itself, as the empty graph $\varepsilon$ has as its vertex and edge set the empty set, both of which are subsets of every set, and $V(G)\subseteq V(G)$ and $E(G)\subseteq E(G)$. Additionally, every subgraph $G'$ of some graph $G$ can be formed from $G$ by a sequence of edge deletions and vertex deletions. Formally, there exists a sequence $G_{0},G_{1},...,G_{n}$ with $G_{0}=G$ and $G_{n}=G'$, and for each $1\leq i\leq n$, it is the case that $G_{i}$ is either formed from $G_{i-1}$ by a single edge removal or a single vertex removal.

Edge contraction

Given a graph $G=(V,E)$, and some edge $e$ between vertices $x,y$ in $G$, the graph formed by contracting the edge $e$ is the graph $G'$ with vertex set equal to $V\setminus \{x,y\}\cup \{v_{xy}\}$, where $v_{xy}$ is the vertex formed by the contraction of $e$, and is adjacent to all neighbours of $x$ and all neighbours of $y$.

Graph minors

Given a graph $G$, and another graph $G'$, $G'$ is called a $TG$ if $G'$ is formed from $G$ by the insertion of vertices of degree two into the edges of $G$. This process is called subdivision, and the vertices of $G$ are known as branch vertices of $G'$, while the other vertices in $G'$ are called subdividing vertices. Now, if some graph $H$ contains a $TG$ as a subgraph, then $H$ is said to have $G$ as a topological minor.

Given a graph $G$, and another graph $G'$, $G'$ is called an $IG$ if $G'$ is formed from $G$ by replacing the vertices of $G$ with connected graphs such that if a vertex $v$ is replaced by a connected graph $G_{v}$, there are edges connecting $G_{v}$ to each of the graphs replacing the vertices that are adjacent to $v$ in $G$, and only to those graphs. This process is called inflation, hence the use of an $I$ to represent it, and the graphs that replace vertices in $G$ are known as the branch sets of $G'$. Now, if some graph $H$ contains an $IG$ as a subgraph, then $H$ is said to have $G$ as a minor, which is denoted as $G\preceq H$.

Theorem: If $G$ is a topological minor of $H$, then $G\preceq H$.

Proof: Since $G$ is a topological minor of $H$, there is some $TG$ a subgraph of $H$. Call that $TG$ $G'$. Number the branch vertices of $G'$ from $1$ to $|G|$. Now, for each subdividing vertex $v$ in $G'$, add $v$ to the branch set containing the branch vertex at minimal distance from $v$. If $v$ has two branch vertices at minimal distance, add it to the branch set containing the branch vertex with lower number. Now, every vertex is in a branch set, and the branch sets are disjoint, and each is connected. This yields an $IG$ that is a subgraph of $H$, and therefore, $G\preceq H$.

Incidence, adjacence, degree

The concept of incidence associates an edge to the nodes that are connected by that edge. For example the edge $\left\{u,v\right\}$ is incident to the nodes $u$ and $v$.

If there is an edge that connects two nodes, we say that those nodes are adjacent. More formally, $u,v\in V(G)$ are adjacent if $\left\{u,v\right\}\in E(G)$. The neighbourhood of a node v, denoted $N(v)$, is the set of all the nodes that are adjacent to it.

The degree of a node v, denoted $\deg(v)$, is the number of edges incident to it. In a directed graph, the in-degree and out-degree count the number of directed edges coming into and out of a vertex respectively.

The minimum degree of a graph $G$, denoted $\delta (G)$, is $\min \limits _{v\in V(G)}d(v)$, the minimum across the vertices of $G$ of the degrees of those vertices.

Similarly, the maximum degree of a graph $G$, denoted $\Delta (G)$, is $\max \limits _{v\in V(G)}d(v)$, the maximum across the vertices of $G$ of the degrees of those vertices.

Handshaking lemma

The handshaking lemma is a consequence of the degree sum formula (also sometimes called the handshaking lemma),

$\sum _{v\in V}\deg(v)=2|E|$

Proof Euler's proof of the degree sum formula uses the technique of double counting: he counts the number of incident pairs $\left\{v,e\right\}$ where e is an edge and vertex v is one of its endpoints, in two different ways. Vertex v belongs to deg(v) pairs, where deg(v) (the degree of v) is the number of edges incident to it. Therefore the number of incident pairs is the sum of the degrees. However, each edge in the graph belongs to exactly two incident pairs, one for each of its endpoints; therefore, the number of incident pairs is 2|E|. Since these two formulas count the same set of objects, they must have equal values.

In a sum of integers, the parity of the sum is not affected by the even terms in the sum; the overall sum is even when there is an even number of odd terms, and odd when there is an odd number of odd terms. Since one side of the degree sum formula is the even number 2|E|, the sum on the other side must have an even number of odd terms; that is, there must be an even number of odd-degree vertices.

Mantel's theorem

The maximum number of edges in an n-vertex triangle-free graph is $\lfloor n^{2}/4\rfloor .$

Proof:

Suppose that $G(V,E)$ is a graph on $n$ vertices. We will find how many edges this graph can have.

For every edge $\left\{u,v\right\}$, if there was a vertex $w$ adjacent to $u$ and to $v$, we would have a triangle. So we know that such vertex does not exist and that the neighbourhood of $u$ is disjoint to the neighbourhood of $v$:

$N(v)\cap N(u)=\emptyset$

This means that any other vertex can be either adjacent to $u$ or adjacent to $v$. When we count degrees of $u$ and $v$, we see that their sum is at most $n$, because a vertex can be counted either as neighbour of $u$ either as neighbour of $v$:

$d(u)+d(v)<n$

The inequality above is valid for every edge. So we have as many inequalities as many edges. If we sum all these inequalities we see that the degree of a vertex $d(v)$ will be there $d(v)$ times, so we have to sum $d(v)^{2}$. The inequality becomes:

$\sum _{v\in V(G)}d(v)^{2}<n\cdot |E(G)|$

Since each edge has two end vertices, the sum of the degrees is exactly twice the number of edges:

$\sum _{v\in V(G)}d(v)=2\cdot |E(G)|$

In $\mathbb {R} ^{n}$ with the standard inner product, the Cauchy–Schwarz inequality is:

$\left(\sum _{i=1}^{n}x_{i}y_{i}\right)^{2}\leq \left(\sum _{i=1}^{n}x_{i}^{2}\right)\left(\sum _{i=1}^{n}y_{i}^{2}\right).$

The two formulas above imply:

$\left(2\cdot |E(G)|\right)^{2}=\left(\sum _{v\in V(G)}d(v)\cdot 1\right)^{2}\leq n\cdot \sum _{v\in V(G)}d(v)^{2}\leq n\cdot (n\cdot |E(G)|)$

Solving for $|E(G)|$ we get:

$|E(G)|\leq n^{2}/4$

Traversals

When examining a graph, quite often we will need to know the various ways to get from one vertex to another, and the different types of traversals this can take. To understand the concept of traversals, we can imagine that the nodes of the graph are squares inside a city, and the edges are the lanes connecting them. Imagine that you have to go by foot from one square to another, and there are some intermediate squares between you and your destination. It is possible to write down the list of all lanes that you have to walk through, the concept of walk is a formalization of that intuitive concept.

Walk, closed walk, circuit and cycle

• A u-v walk is defined as a sequence of vertices starting at u and ending at v, where consecutive vertices in the sequence are adjacent vertices in the graph

  

  A drawing of a labelled graph on 6 vertices and 7 edges.

  • A closed walk is a walk in which the first and last vertices are the same
• A u-v trail is a u-v walk, where no edge is repeated (each edge is used at most once)
  • A circuit or closed trail is a trail in which the first and last vertices are the same
• A u-v path is a u-v walk, where no vertex is repeated (each vertex is used at most once)
  • A cycle is a closed path in which the first and last vertices are the same

For example, in the image to the right, $(6,4,5,1)$ is a walk. While $(4,5,2,3,4)$, and $(1,5,2,1)$ are cycles.

Distance in a Graph

Now, we need to define a concept of distance in a graph; this helps us encode more data in the graph.

Length of a walk

the number of edges used in a particular walk.

If an edge is used more than once, then it is counted more than once.
A trivial walk is one where the length is 0.

Theorem

If a graph G contains a u-v walk of length $\ell$, then G contains a u-v path of length ≤$\ell$.

Proof:

Let P be a u-v walk of shortest length. We claim that P is a path (since being the shortest, it eliminates repeated vertices).

Suppose not. Suppose that P is not a path. Then, at least one vertex is repeated (used twice). Then, set $P:u=u_{0},u_{1},\ldots ,u_{\ell }=v$, where $\ell$ is the length of P.

And, we know that $u_{i}=u_{j}$ for some $0\leq i<j\leq \ell$.

Then, remove the repeated vertex(ices) to get $P':u=u_{0},u_{1},\ldots ,u_{i},u_{j+1},\ldots ,u_{\ell }=v$. But, then we get that the length of P' is smaller than the length of P, which contradicts our assumption that P was the walk of shortest length.

So, P must be a path, and it is shorter than any other walk that has vertices in P.

Thus, there is a u-v path of length at most $\ell$.

Graph Distance

The graph distance $d(u,v)$ between two vertices $u$ and $v$ of a finite graph is the minimum length of the paths connecting them. The length of a graph geodesic, too.
A geodesic is a shortest path between two graph vertices $(u,v)$ of a graph.
If no such path exists ( if the vertices lie in different connected components ), then the distance is set equal to $\infty$.

Geodesics

For any two vertices u and v in a graph G, the distance between u and v is defined to be the length of the shortest path between u and v, denoted d(u,v).

A path of length d(u,v) is called a geodesic.

Properties of d(u,v):
For a geodesic P:u=u₀u₁u₂...u_k=v and some 0≤i,j≤k:

1. d(u₀u_k) = k
2. d(u_iu_i) = 0 (not travelling anywhere)
3. d(u₀u_i) = i
4. d(u_iu_j) = |j-i|

More Graph Parameters

Using d(u,v), we can find other parameters of the graph G:

• Diameter: the diameter diam(G) is the largest distance d(u,v) between any two vertices of a connected graph; i.e. diameter is the max{d(u,v)} for all sets of u,v in V(G).

Graph Eccentricity

The eccentricity $\epsilon (v)$ of a graph vertex $v$ in a connected graph $G$ is the maximum graph distance between $v$ and any other vertex $u$ of $G$.
For a disconnected graph, all vertices are defined to have infinite eccentricity.

• Graph Diameter : The maximum graph eccentricity
• Graph Radius : The minimum graph eccentricity

Connectivity

Whether or not it is possible to traverse a graph from one vertex to another is dependent on how connected a graph is.

Definition of Connectedness

1. If there is a u-v path in G, then we say that u and v are connected
2. If there is a u-v path for every pair of vertices u and v in G, then we say that G is connected

Theorems on Connectedness

Theorem: Let G be a graph of order at least 3. If there are distinct vertices u and v in G so that G-u and G-v are both connected, then G is also connected.

Proof: Let w be a G vertex, which is different from both u and v. We want to prove connectedness, i.e., that for every pair (x,y) of vertices in G, there is an x-y walk in G. We may consider three (partly overlapping) cases:

• If neither x nor y is u, then there is an x-y walk in G-u, and this also is an x-y walk in G.
• If neither x nor y is v, then there is an x-y walk in G-v, and this also is an x-y walk in G.
• If {x,y} = {u,v}, then employ the first two cases in order to see that there is a u-w walk and a w-v walk. Combining them indeed yields a u-v walk.

Vertex and Edge Connectivity

A graph G is called k-connected if for every $S\subseteq V(G)$, and $|S|<k$, $G-S$ is connected, and $|G|>k$.

Similarly, a graph G is called $\ell$ edge-connected if for every $S\subseteq E(G)$, and $|S|<\ell$, $G-S$ is connected, and $|G|>1$.

The connectivity of G is the greatest k such that G is k-connected, and is denoted by $\kappa (G)$.

Relatedly, the edge-connectivity of G is the greatest $\ell$ such that G is $\ell$ edge-connected, and is denoted by $\lambda (G)$.

Theorems on Connectivity

Theorem: Let G be a k-connected graph. Then, $\forall i\in \mathbb {N} ,0\leq i\leq k$, G is i-connected.

Proof: Since G is k-connected, for all $S\subseteq V(G),|S|<k$, $G-S$ is connected. Then, since $i\leq k$, for all $S\subseteq V(G),|S|<i\leq k$, $G-S$ is also connected.

Theorem: Let G be a nontrivial graph. Then, $\lambda (G)\leq \delta (G)$.

Proof: Take v a vertex of degree $\delta (G)$ in G. Then, removing all edges in G that are incident with v disconnects v from the rest of the graph, provided that $|G|>\delta (G)+1$. Therefore, G cannot be $\delta (G)$ edge-connected, and so $\lambda (G)\leq \delta (G)$.

Exercise: Connectivity If G is $\ell$ edge-connected, show that G is also i edge-connected $\forall i\in \mathbb {N} ,0\leq i\leq \ell$.

Isomorphism

An isomorphism of graphs G and H is a bijection between the vertex sets of G and H

$f\colon V(G)\to V(H)\,\!$

such that any two vertices u and v of G are adjacent in G if and only if ƒ(u) and ƒ(v) are adjacent in H. This kind of bijection is commonly called "edge-preserving bijection", in accordance with the general notion of isomorphism being a structure-preserving bijection.

In the above definition, graphs are understood to be undirected non-labeled non-weighted graphs. However, the notion of isomorphism may be applied to all other variants of the notion of graph, by adding the requirements to preserve the corresponding additional elements of structure: arc directions, edge weights, etc., with the following exception. When spoken about graph labeling with unique labels, commonly taken from the integer range 1,...,n, where n is the number of the vertices of the graph, two labeled graphs are said to be isomorphic if the corresponding underlying unlabeled graphs are isomorphic.

If an isomorphism exists between two graphs, then the graphs are called isomorphic and we write $G\simeq H$. In the case when the bijection is a mapping of a graph onto itself, i.e., when G and H are one and the same graph, the bijection is called an automorphism of G.

The graph isomorphism is an equivalence relation on graphs and as such it partitions the class of all graphs into equivalence class es. A set of graphs isomorphic to each other is called an isomorphism class of graphs.

Example

The two graphs shown below are isomorphic, despite their different looking drawings.

Graph G	Graph H	An isomorphism between G and H
		ƒ(a) = 1 ƒ(b) = 6 ƒ(c) = 8 ƒ(d) = 3 ƒ(g) = 5 ƒ(h) = 2 ƒ(i) = 4 ƒ(j) = 7

Motivation

The formal notion of "isomorphism", e.g., of "graph isomorphism", captures the informal notion that some objects have "the same structure" if one ignores individual distinctions of "atomic" components of objects in question, see the example above. Whenever individuality of "atomic" components (vertices and edges, for graphs) is important for correct representation of whatever is modeled by graphs, the model is refined by imposing additional restrictions on the structure, and other mathematical objects are used: digraphs, labeled graphs, colored graphs, rooted trees and so on. The isomorphism relation may also be defined for all these generalizations of graphs: the isomorphism bijection must preserve the elements of structure which define the object type in question: arcs, labels, vertex/edge colors, the root of the rooted tree, etc.

The notion of "graph isomorphism" allows us to distinguish graph properties inherent to the structures of graphs themselves from properties associated with graph representations: graph drawings, data structures for graphs, graph labelings, etc. For example, if a graph has exactly one cycle, then all graphs in its isomorphism class also have exactly one cycle. On the other hand, in the common case when the vertices of a graph are (represented by) the integers 1, 2,... N, then the expression

$\sum _{v\in V(G)}v\cdot {\text{deg }}v$

may be different for two isomorphic graphs.

Complement

The Petersen graph (on the left) and its complement graph (on the right).

The complement or inverse of a graph G is a graph H on the same vertices such that two vertices of H are adjacent if and only if they are not adjacent in G. That is, to generate the complement of a graph, one fills in all the missing edges required to form a complete graph, and removes all the edges that were previously there. It is not, however, the set complement of the graph; only the edges are complemented.

Formal construction

The complement of a graph $G=(V,E)$ is a graph ${\bar {G}}=(V,E')$ such that for all pairs of vertices $u,v\in G$, there is an edge $(u,v)\in E'$ if and only if $(u,v)\not \in E$. If we let $K=V\times V$, we see that $E'=K\setminus E$.

Applications and examples

Several graph-theoretic concepts are related to each other via complement graphs:

• The complement of an edgeless graph is a complete graph and vice versa.
• The complement of any triangle-free graph is a claw-free graph.
• A self-complementary graph is a graph that is isomorphic to its own complement.
• Cographs are defined as the graphs that can be built up from disjoint union and complementation operations, and form a self-complementary family of graphs: the complement of any cograph is another (possibly different) cograph.

Tree

A tree is a type of connected graph. An directed graph is a tree if it is connected and has no cycles. An undirected graph is considered a tree if it is connected, has $|V|-1$ edges and is acyclic (a graph that satisfies any two of these properties satisfies all three).

Exercise: Equivalent Definitions Show that the following are equivalent definitions for a tree: A graph with a minimal number of edges which is connected. A graph with maximal number of edges without a cycle. A graph with no cycle in which adding any edge creates a cycle. A graph with n nodes and n-1 edges that is connected. A graph in which any two nodes are connected by a unique path (path edges may only be traversed once). Hint: To keep the total proof short, put the definitions in a suitable order, and then prove A=>B=>C=>D=>E=>A. Take particular care over graphs with zero and one node.

Rooted tree

A tree is called a rooted tree if one vertex has been designated the root, in which case the edges have a natural orientation, towards or away from the root. The tree-order is the partial ordering on the vertices of a tree with u ≤ v if and only if the unique path from the root to v passes through u. A rooted tree which is a subgraph of some graph G is a normal tree if the ends of every edge in G are comparable in this tree-order whenever those ends are vertices of the tree.

In a rooted tree, the parent of a vertex is the vertex connected to it on the path to the root; every vertex except the root has a unique parent. A child of a vertex v is a vertex of which v is the parent.

In a rooted tree and all vertices have at most one parent.

Complete graph

A complete graph is one for which all pairs of vertices are connected by an edge. A complete graph on $n$ vertices is denoted $K_{n}$.

Any graph that has a subgraph isomorphic to $K_{5}$ is non-planar.

Exercise: Planarity Can $K_{5}$ be drawn on the surface of a torus? Can $K_{5}$ be drawn on the surface of a Klein bottle?

Exercise: Subgraphs and Isomorphisms How many distinct copies of $K_{n}$ are contained in $K_{n+1}$? How many automorphisms of $K_{n}$ are there?

Bipartite graph

A graph $G=(V,E)$ is bipartite if the vertex set $V$ can be partitioned into two disjoint subsets such that for every edge $(u,v)\in E$, $u$ and $v$ are in opposite subsets.

Additionally, a graph is bipartite if and only if it contains no odd cycles.

Proof:

Let $G=(V,E)$ be an arbitrary and fixed graph with an odd cycle.

$G$ is bipartite $\Longrightarrow G$ contains no odd cycles

Assume for the sake of contradiction that $G$ contains an odd cycle.

Let $G_{1},G_{2}$ be two disjoint subsets that form a bipartition on $G$.

Choose an odd cycle $C$ in $G$and, without loss of generality, choose some node $v_{1}\in C$ from $G_{1}$. Traverse $C$ starting from $v_{1}$, noting that each node is in the different subset $G_{1},G_{2}$ from its neighbors by definition of a bipartite graph.

The last node in this traversal, $v_{n}$, must be in $G_{1}$, as $C$ is an odd cycle. However, $v_{n}$ is adjacent to $v_{1}$ by definition of a cycle, which is a contradiction as $G_{1}$ contains two adjacent nodes, so $G$ cannot contain an odd cycle.

As we have looked at an arbitrary $C$ and chose $v$ without loss of generality from $G_{1}$, we have proven the implication.

$G$ contains no odd cycles $\Longrightarrow G$ is bipartite

We present an algorithm to sort the nodes into two disjoint sets.

• Fix an arbitrary node $v\in V$.
• For each node $x$ in the graph, calculate the shortest path from $x$ to $v$.
• Let $A,B$ be the sets of nodes such that the shortest path from $x$ to $v$ are even and odd respectively.

We look without loss of generality at $A$ to prove this algorithm's correctness.

Assume for the sake of contradiction two nodes $v_{1},v_{2}\in A$ are adjacent. Let $P_{1},P_{2}$ represent the shortest paths from $v$ to $v_{1},v_{2}$ respectively.

• If $P_{1}$ and $P_{2}$ do not intersect, $P_{1},(v_{1},v_{2}),P_{2}$ forms a cycle of odd length as $P_{1}$ and $P_{2}$ trivially have the same parity, which is a contradiction.
• If $P_{1}$ and $P_{2}$ intersect, we choose the intersection $v'$ closest to $v_{1}$. Note $v'$ cannot be either $v_{1}$ or $v_{2}$, as the shortest paths from $v_{1}$ to $v_{2}$ would not have the same parity. Observe that the distance from $v'$ to $v_{1}$ and $v_{2}$ must be the same length, otherwise the shortest path to either $v_{1},v_{2}$ would travel through the other node. However, this is a contradiction as $(v',v_{1}),(v_{1},v_{2}),(v',v_{2})$ would be an odd cycle.

Therefore, no two nodes in $A$ can be adjacent, and as we looked at $A$ without loss of generality, we have proven the algorithm correct and therefore the reverse implication.

Complete Bipartite Graph

The complete bipartite graph $K_{m,n}$ is the graph composed of two disjoint subsets $A,B$ of cardinality $m,n$ respectively, such that $K_{m,n}$ contains an edge between each node in $A$ and every node in $B$.