Before we give the definition of a graph, we introduce the following useful notation. For any set \(S\) we denote by \(\binom{S}{2}\) the set of all two-element subsets of \(S\), that is,
\[
\binom{S}{2} = \big\{ \{u, v\} \,|\, u, v \in S,\; u\neq v\big\}.
\]
If \(S\) is finite and contains \(n=|S|\geq 1\) elements then the number of elements of \(\binom{S}{2}\) is
\[
\binom{n}{2} = \frac{n!}{2!(n-2)!} = \frac{n(n-1)}{2}.
\]
For instance, if \(S=\{v_1,v_2,v_3,v_4\}\) then
\[
\binom{S}{2} = \big\{\set{v_1,v_2}, \set{v_1,v_3}, \set{v_1,v_4},\set{v_2,v_3},\set{v_2,v_4},\set{v_3,v_4} \big\}.
\]
and the number of elements of \(\binom{S}{2}\) is \(\binom{4}{2}=\frac{4\cdot 3}{2}=6\). We are now ready to define a graph.
A graph \(G\) consists of two sets \(V\) and \(E\) where \(E\) is some subset of \(\binom{V}{2}\). The set \(V\) is called the vertex set of \(G\) and \(E\) is called the edge set of \(G\). In this case we write \(G=(V,E)\).
Let \(G=(V,E)\) be a graph. The elements of \(V\) are called the vertices of \(G\) and the elements of \(E\) are called the edges of \(G\). We will frequently use the notation \(V(G)\) and \(E(G)\) to denote the vertex set and edge set, respectively, of \(G\). If \(V\) is a finite set, then \(G\) is called a finite graph. In this book, we consider only finite graphs.
A graph can be used to encode some relationship of interest between entities. The entities are represented by the vertices and two vertices \(u\) and \(v\) form an edge \(\set{u,v}\) in the graph if \(u\) and \(v\) are ``related''. The condition for being ``related'' might be that \(u\) and \(v\) are friends in a social network, or \(u\) and \(v\) are subway stations that are directly linked by a train, or \(u\) and \(v\) are cells in a biological network that are biologically linked in some energy transfer, etc.
Sometimes, it is useful to think of a graph as a collection of points connected by lines (or curves) in the 2D-plane. One can visualize a graph \(G=(V,E)\) by drawing a point on the 2D plane for each vertex and then connecting vertices \(u\) and \(v\) with a line if and only if \(\{u,v\} \in E\). As an example, a visual representation of the graph \(G\) with vertex set \(V=\{x,y,z,w\}\) and edge set \(E=\{\set{x,y},\set{x,z},\set{y,z},\set{z,w}\}\) is shown in Figure 1.1. Although a visual representation of a small graph might be useful, it is important to remember that a graph is just a pair of sets \(V\) and \(E\) where \(E\subset \binom{V}{2}\).
Visual representation of the graph \(G=(V,E)\) with vertex set \(V=\{x,y,z,w\}\) and edge set \(E=\{\set{x,y},\set{x,z},\set{y,z},\set{z,w}\}\)
Consider the graph \(G\) shown in Figure 1.2. Based on this graphical representation of \(G\), what is \(V(G)\) and \(E(G)\)?
For this graph \(G\), what is \(V(G)\) and \(E(G)\)?
Let \(G=(V,E)\) be the graph with vertex set \(V=\{2,3,\ldots,10\}\) and edge set
\[
E = \set{ \set{u,v} \;|\; \gcd(u,v) \geq 2}.
\]
What is the edge set \(E\) and how many edges does \(G\) have? Draw a visual representation of \(G\).
Check-out the Wiki page on \href{https://en.wikipedia.org/wiki/Graph_theory}{Graph theory}.
Exercises
Let \(G=(V,E)\) be the graph with vertex set \(V=\{2,3,\ldots,10\}\) and edge set
\[
E = \{\set{u,v} \;|\; \gcd(u,v) = 1\}.
\]
Write out the edge set \(E\) and draw the graph \(G\). How many edges does \(G\) have? Aside from having the same vertex set, what is the relationship between the graph in this exercise and the graph in Example 1.2?
Let \(V\) be the set of \(3\)-dimensional binary vectors. In other words, an element of \(V\) is of the form \(\bs{b}=(b_1,b_2,b_3)\) where \(b_i\) is either zero or one. Let \(G=(V,E)\) be the graph with edge set \(E\) consisting of edges formed by two binary vectors that differ at only a single entry. For example, if \(\bs{b}_1=(1,0,1)\) and \(\bs{b}_2=(1,0,0)\) then \(\set{\bs{b}_1,\bs{b}_2}\) is an edge of \(G\) since \(\bs{b}_1\) and \(\bs{b}_2\) differ only in the third entry, whereas if \(\bs{b}_1=(0,1,1)\) and \(\bs{b}_2=(1,0,0)\) then \(\set{\bs{b}_1,\bs{b}_2}\) is note an edge of \(G\). Do the following:
Explicitly write out the vertex set \(V\). How many vertices are there?
Explicitly write out the edge set \(E\). How many edges are there?
Make a visual representation of \(G\) in the 2D plane. (Do not read part (d) yet!)
Now make a visual representation of \(G\) in a 3D coordinate system by drawing each vertex \(\bs{b}=(b_1,b_2,b_3)\) as a point in \(\real^3\).
Consider the following list \(\sigma=(5,2,6,1,7,3,4)\) and let \(V=\{1,2,\ldots,7\}\). Let \(G=(V,E)\) be the graph such that \(\{i, j\} \in E\) if and only if the numbers \(i\) and \(j\) appear in reverse order in \(\sigma\). For example, \(\{1,3\}\notin E\) because \(1\) appears before \(3\) and so are in correct order, whereas \(\{3,6\}\in E\) because \(6\) appears before \(3\) in \(\sigma\) and so are in reverse order. Write out the edge set \(E\) and draw a visual representation of \(G\).
What are some real-world systems that can be modeled as graph? What are the vertices and when would two vertices form an edge?
The rudiments of graph theory
Let us now introduce same basic terminology associated with a graph. The order of a graph \(G\) is the cardinality of the vertex set \(V\) and the size of \(G\) is the cardinality of the edge set. Usually, we use the variables \(n=|V|\) and \(m=|E|\) to denote the order and size of \(G\), respectively.
Given two vertices \(u, v\in V\), we say that \(u\) and \(v\) are adjacent or neighbors if \(\{u,v\} \in E\). In this case, we will write \(u\sim v\) to denote adjacency and, whenever it is convenient to do so, we will denote the 2-element set \(\{u,v\}\) by simply \(uv\). Given an edge \(e = uv \in E\), we will simply say that \(u\) and \(v\) are the vertices of the edge \(e\). If \(u\in e\) we say that \(u\) is incident with \(e\) and that \(e\) is incident with \(u\). The neighborhood of \(v\in V\), denoted by \(N(v)\), is the set of all vertices adjacent to \(v\), in other words
\[
N(v) = \{ u\in V\;|\; u\sim v\} = \{ u\in V\;|\; \{u,v\}\in E\}.
\]
The degree of a vertex \(v\), denoted by \(\deg(v)\), is the cardinality of \(N(v)\), that is, the number of neighbors of \(v\). It is clear that \(0\leq \deg(v)\leq n-1\) for all \(v\in V(G)\). A vertex \(v\) with \(\deg(v) = n-1\) is called a dominating vertex and if \(\deg(v) = 0\) then \(v\) is called an isolated vertex. The maximum/minimum degree of a graph \(G\) is the maximum/minimum degree among all vertices of \(G\). The maximum degree of \(G\) is denoted by \(\Delta(G)\) and the minimum degree is denoted by \(\delta(G)\), in other words
\[
\Delta(G) = \max\set{\deg(v)\;|\; v \in V }
\]
and
\[
\delta(G) = \min\set{\deg(v)\;|\; v \in V}.
\]
It is clear that \(0\leq \delta(G) \leq \Delta(G)\leq n-1\). The degree sequence of a graph \(G\), denoted by \(d(G)\), is the sequence of the vertex degrees of \(G\) listed in decreasing order. Hence, if \(n=|V(G)|\) then the degree sequence of \(G\) is of the form \(d(G) = (d_1, d_2, \ldots, d_n)\) where \(d_1\geq d_2 \geq d_3\geq \cdots \geq d_n\).
Find \(N(v_4)\), \(N(v_6)\), \(N(v_{10})\) and \(\deg(v_4), \deg(v_6)\), and \(\deg(v_{10})\).
Find \(\Delta(G)\) and \(\delta(G)\).
Find the degree sequence \(d(G)\).
Find \(\sum_{i=1}^n \deg(v_i)\) and compare it with \(m\).
The last part of the previous example is known as the Handshaking Lemma.
For any graph \(G=(V,E)\) it holds that
\[
\sum_{v\in V} \deg(v) = 2|E|.
\]
Consequently, in any graph the number of vertices with odd degree is even.
The degree of \(v\) counts the number of edges incident with \(v\). Since each edge is incident with exactly two vertices, the sum \(\sum_{v\in V} \deg(v)\) counts each edge twice, and therefore \(\sum_{v\in V} \deg(v)= 2|E|\). It follows then that the number of vertices \(v\) with odd degree \(\deg(v)\) is even.
Another property of the degree sequence is the following.
In any graph \(G\) there are at least two vertices with equal degree.
Let \(G\) be any graph of order \(n\) with degree sequence
\[
d(G) = (d_1, d_2,\ldots, d_n).
\]
We consider two mutually exclusive cases. In the first case, if \(\delta(G) = 0\) then \(\Delta(G) \leq n-2\). Hence, \(0\leq d_i \leq n-2\) for every \(i=1,2,\ldots, n\), and then by the pigeon-hole principle there is at least two degrees that are equal. On the other hand, if \(\delta(G) \geq 1\) then \(1\leq d_i \leq n-1\) for every \(i=1,2,\ldots,n\), and then again by the pigeon-hole principle there are at least two equal degrees.
Explain why in every social gathering there are at least two persons who are friends with the same number of persons.
Let \(V\) be a finite set with cardinality \(n=|V|\). How many distinct graphs are there with vertex set \(V\)? Let us first consider two extreme cases. The empty graph on \(V\), which we will denote by \(E_n\), is the graph whose edge set is the empty set, that is, \(E(E_n) = \emptyset\). A visual representation of the empty graph consists of \(n\) points in the plane with no edges among the vertices. At the other extreme, the complete graph, which we will denote by \(K_n\), is the graph in which each vertex is adjacent to all other vertices. Hence, in the complete graph \(K_n\), every possible edge is present. The total number of possible edges in a graph with \(n\) vertices is \(M=\binom{n}{2}\). For example, if \(V=\{v_1,v_2,v_3,v_4\}\) then the set of all 2-element subsets of \(V\) is
\[
\binom{V}{2} = \big\{\set{v_1,v_2}, \set{v_1,v_3}, \set{v_1,v_4},\set{v_2,v_3},\set{v_2,v_4},\set{v_3,v_4} \big\}
\]
and in this case \(\binom{4}{2} = 6\), which is the cardinality of \(\binom{V}{2}\). Now, recall that by definition of a graph, the edge set is a subset of \(\binom{V}{2}\). Hence, the total number of distinct graphs with vertex set \(V\) is equal to the number of subsets of \(\binom{V}{2}\). The number of subsets of a set with \(M\) elements is \(2^M\). Applying this to the set \(\binom{V}{2}\) we conclude that the number of graphs with vertex set \(V\) is therefore \(2^M = 2^{\binom{n}{2}}\) where \(n=|V|\).
If \(V\) is a set with \(n\) elements then the number of distinct graphs with vertex set \(V\) is \(2^{\binom{n}{2}}\).
How many graphs are there with vertex set \(V=\{1,2,3\}\)? Draw all of them and group them by the number of edges in the graph.
Let \(V\) be a finite set with cardinality \(n=|V|\). How many graphs are there on \(V\) that have exactly \(m\) edges? Note that necessarily \(0\leq m\leq \binom{n}{2}\). Use your result to obtain a formula for \(2^{\binom{n}{2}}\).
The complement of a graph \(G=(V,E)\) is the graph \(\overline{G}\) with the same vertex set as \(G\) and whose edge set consists of all edges not present in \(G\). In other words, \(E(\overline{G}) = \binom{V}{2}\backslash\hspace{-0.3em} E(G)\). It follows then that \(|E(G)| + |E(\overline{G})| = \binom{n}{2}\).
Let \(G=(V,E)\) be the graph with \(V(G)=\{1,2,3,4,5,6\}\) and
\[
E(G)=\{\set{1,2},\set{1,3},\set{2,3},\set{2,6},\set{3,4},\set{4,5},\set{4,6}\}.
\]
What is \(E(\overline{G})\)? Draw both \(G\) and \(\overline{G}\).
If \(G\) is a graph of order \(n=17\) and \(\deg_G(v) = 9\) then what is \(\deg_{\overline{G}}(v)\)? Here we are using the notation \(\deg_G(v)\) to denote the degree of \(v\) in the graph \(G\) and \(\deg_{\overline{G}}(v)\) the degree of \(v\) in \(\overline{G}\). In general, what is \(\deg_{\overline{G}}(v)\) in terms of \(n=|V|\) and \(\deg_G(v)\)?
A graph \(G\) is said to be \(k\)-regular if every vertex in \(G\) has degree \(k\). If \(G\) is \(k\)-regular then clearly \(k = \delta(G) = \Delta(G)\). Conversely, given any graph \(G\) if \(\delta(G) = \Delta(G)\) then \(G\) is a regular graph.
Prove that if \(G\) is \(k\)-regular then \(\overline{G}\) is also regular. What is the degree of each vertex in \(\overline{G}\)?
Draw a \(3\)-regular graph on \(n=6\) vertices.
Is there a \(k\)-regular graph on \(n\) vertices if \(n=11\) and \(k=3\)? To answer this question, prove that if \(G\) is a \(k\)-regular graph on \(n\) vertices then \(nk\) must be even. Hint: Use the Handshaking lemma.
A graph \(H=(V(H), E(H))\) is said to be a subgraph of \(G=(V(G),E(G))\) if \(V(H) \subset V(G)\) and \(E(H)\subset E(G)\). For any subset of vertices \(W\subset V(G)\), the subgraph induced by \(W\), denoted by \(G[W]\), is the subgraph of \(G\) with vertex set \(W\) and edge set
\[
E(G[W]) = E(G) \cap \binom{W}{2}.
\]
In other words, the subgraph \(G[W]\) contains all edges of \(G\) whose end-vertices are in \(W\). The following example will make clear the difference between a subgraph and an induced subgraph.
Consider again the graph in Figure 1.2. You can verify that the graph \(H\) with \(V(H) = \{v_2, v_3, v_4, v_6, v_8, v_9\}\) and edge set \(E(H) = \{v_2v_4, v_3v_4,v_4v_9, v_4v_6, v_8v_9\}\) is a subgraph of \(G\). However, it is not an induced subgraph. The subgraph of \(G\) induced by the vertices \(W= \{v_2, v_3, v_4, v_6, v_8, v_9\}\) (that is, the graph \(G[W])\) has edge set
\[
E(G[W]) = \{v_2v_4, v_3v_4, v_4v_6,v_4v_8,v_4v_9,v_6v_8,v_6v_9,v_8v_9\}.
\]
A subgraph \(H=(V(H), E(H))\) of \(G\) is called a path in \(G\) if we can order the vertices of \(H\), say \((w_0, w_1, \ldots, w_r)\), such that \(w_{i-1} \sim w_i\) for \(i=1,2,\ldots, r\). We also say that \(H\) is a path from the vertex \(w_0\) to \(w_r\) and that the length of the path \(H\) is \(r\). As an example, \((v_1, v_3, v_4, v_8, v_7, v_6, v_9)\) is a path of length six in the graph in Figure 1.2. A graph \(G\) is said to be connected if for any distinct vertices \(u, v\in V(G)\) there exists a path from \(u\) to \(v\), and is called disconnected otherwise. A connected component of a graph \(G\) is an induced subgraph \(H=G[W]\) such that \(H\) is connected and \(H\) is not a proper subgraph of a connected subgraph of \(G\). From these definitions, it is straightforward to show that a graph \(G\) is connected if and only if it contains only one connected component.
Draw a graph on \(n=8\) vertices with \(m=5\) edges having 3 connected components.
Prove that if \(G\) is disconnected then \(\overline{G}\) is connected. Give an example of a connected graph \(G\) such that \(\overline{G}\) is also connected. Hint: There is one for \(n=4\) and several for \(n=5\).
Having defined the length of a path, we define the distance between vertices.
The distance between vertices \(u, v \in G\) is the length of a shortest path from \(u\) to \(v\) (or equivalently from \(v\) to \(u\)). We denote the distance between \(u\) and \(v\) as \(d_G(u,v)\), and if the graph \(G\) is understood simply by \(d(u,v)\). If there is no path in \(G\) from \(u\) to \(v\) then \(d(u,v)\) is not defined.
Let \(H\) be a connected subgraph of the connected graph \(G\) and let \(u\) and \(v\) be vertices of \(H\). Prove that \(d_G(u,v) \leq d_H(u,v)\).
Lastly, the diameter of a connected graph \(G\), denoted by \(\diam(G)\), is the maximum distance among all the vertices in \(G\), in other words
\[
\diam(G) = \max\set{d(u,v)\;|\; u, v \in V(G),\, u\neq v }.
\]
If \(H\) is a connected subgraph of a connected graph \(G\), what is the relationship between \(\diam(H)\) and \(\diam(G)\)? To answer this question consider the following.
Give an example of \(H\) and \(G\) such that \(\diam(H) = \diam(G)\).
Give an example of \(H\) and \(G\) such that \(\diam(H) \lt \diam(G)\).
Give an example of \(H\) and \(G\) such that \(\diam(H) \gt \diam(G)\).
Suppose that \(d_H(u,v) = d_G(u,v)\) for all vertices \(u, v \in V(H)\). Prove that \(\diam(H) \leq \diam(G)\).
Exercises
How many graphs are there with vertex set \(V=\{1,2,\ldots, 8\}\)? How many of these have \(m=14\) edges?
Let \(G\) be a graph with \(n=|V(G)|\) and \(m=|E(G)|\). Show that
\[
\delta(G) \leq \tfrac{2m}{n}\leq \Delta(G).
\]
What statistical measure of the vertex degrees is \(\frac{2m}{n}\)?
Let \(V\) be the set of all Hollywood actors and let \(G=(V,E)\) be the graph where \(\set{u,v} \in E\) if and only if \(u\) and \(v\) have appeared in the same Hollywood film.
For \(v\in V\), what does \(\deg(v)\) represent?
If \(v\) is such that \(\deg(v) = 0\), what can we say about the actor \(v\) and the film(s) \(v\) has appeared in?
If \(v\) is such that \(\deg(v) = 1\), what can we say about the actor \(v\) and the film(s) \(v\) has appeared in?
What does \(\Delta(G)\) represent?
If \(G\) has degree sequence \(d(G) = (d_1, d_2, \ldots, d_n)\), what is the degree sequence of \(\overline{G}\)?
Draw a graph with degree sequence \(d=(4,4,4,4,1,1,1,1)\).
For each case, decide whether or not a graph can have the given degree sequence. Justify your answers.
\(d=(3,3,2,1)\)
\(d=(3,2,1,0)\)
\(d=(4,4,2,1)\)
\(d=(2,2,2,2)\)
Draw the complement of the graph \(G\) shown below:
For the graph shown in Figure 1.3 with vertex set \(V=\set{v_1,v_2,\ldots, v_{11}}\), decide if the given subgraph \(H=(V(H), E(H))\) is induced. Explain your answer.
For the graph \(G\) in Figure 1.3, determine a path from \(v_2\) to \(v_9\). What is the length of the path? Do the same for vertices \(v_8\) to \(v_{11}\). What is \(\diam(G)\)?
How many edges in a graph guarantee that it is connected? To answer this question, show the following.
Let \(G\) be a graph with \(n\geq 2\) vertices and \(m\) edges. Show that if \(m \geq \binom{n-1}{2}+1\) then \(G\) is connected. Hint: Try this for small \(n\).
Show that for each \(n \geq 1\), there exists a graph with \(m = \binom{n-1}{2}\) edges that is disconnected.
Conclude that \(\binom{n-1}{2} + 1\) is the least number of edges that guarantee that \(G\) is connected.
Give an example of a connected graph \(G\) with fewer than \(\binom{n-1}{2}\) edges.
Show by example that if \(G\) is connected then \(\overline{G}\) can be disconnected.
Prove that if \(\delta(G)\geq \frac{n-1}{2}\) then \(G\) is a connected graph, where as usual \(n=|V(G)|\). Prove also that \(\diam(G)\leq 2\).
Permutations
In this section, we pause our introduction to graph theory so that we can introduce some background material on permutations. We will need to be fluent with the rudiments of permutations in the next section when we consider the very important notion of graph isomorphisms and automorphisms.
The set of permutations on a set is an example of a group. Usually, groups are denoted with the letters \(G\) or \(H\) but since these are usually the letters used for graphs, we will use instead the symbol \(\Gamma\) to denote a generic group. Let us recall the definition of a group.
A group is a set \(\Gamma\) and a binary operation defined on \(\Gamma\), denoted by \(\star:\Gamma\times\Gamma\rightarrow\Gamma\), that satisfies the following:
For all \(a,b,c\in\Gamma\) it holds that \((a\star b)\star c = a \star (b\star c)\) (associativity)
There is an element \(e\in\Gamma\) such that \(a\star e = a\) and \(e\star a = a\) for every \(a\in\Gamma\). The element \(e\) is called the identity element.
For each \(a\in\Gamma\) there exists an element \(b\in\Gamma\) such that \(a\star b = e\) and \(b\star a = e\). Usually, \(b\) is denoted instead by \(a^{-1}\) so that \(a\star a^{-1} = a^{-1}\star a = e\), and \(a^{-1}\) is called an inverse of \(a\).
In many cases, the group operation \(a\star b\) is a sort of product operation in which case the product \(a\star b\) is denoted simply as \(ab\). Sometimes, however, the group operation is a sort of addition operation and so in that case \(a\star b\) would be denoted by \(a+b\). The essential feature, however, is that \(a\star b\) is a binary operation that satisfies the listed properties (i)-(iii). Before we give examples of groups, we give the following definition.
A group \(\Gamma\) with group operation \(\star:\Gamma\times\Gamma\rightarrow\Gamma\) is said to be an abelian group if the group operation is commutative, that is, if \(a\star b = b\star a\) for every \(a,b\in\Gamma\).
The integers \(\mathbb{Z}\) with the operation of addition forms a group. Indeed, addition is an associative operation; if \(a,b,c\in\mathbb{Z}\) then \((a+b) + c = a + (b+c)\). The identity element of \(\mathbb{Z}\) is zero because \(a+0 = 0 + a = a\) for every \(a\in\mathbb{Z}\). Lastly, for each \(a\in\mathbb{Z}\) its inverse under addition is \(-a\), and since \(-a\in\mathbb{Z}\) it follows that every \(a\in\mathbb{Z}\) has an inverse in \(\mathbb{Z}\). Hence, \(\mathbb{Z}\) with operation \(+\) is a group. Since addition of integers is commutative, the group \((\mathbb{Z}, +)\) is an abelian group.
The integers \(\mathbb{Z}\) with the operation of multiplication is not a group. What property of a group does \(\mathbb{Z}\) not satisfy when the operation is multiplication?
Consider the finite set \(\Gamma=\{1,-1,i,-i\}\) where \(i\) satisfies \(i^2 = -1\). Then \(\Gamma\) is a group under multiplication. Multiplication of real or complex numbers is an associative operation. You can verify that multiplication is a binary operation on \(\Gamma\), that is, whenever we take two elements in \(\Gamma\) and multiply them we obtain an element back in \(\Gamma\). The identity element is the number \(1\). Lastly, every element in \(\Gamma\) has an inverse that is in \(\Gamma\). For example, the inverse of \(i\in\Gamma\) is \(-i\in \Gamma\) because \(i\cdot (-i) = - i^2 = -(-1) = 1\). As another example, the inverse of \(-1\in\Gamma\) is itself because \(-1\cdot -1 = 1\). Is \(\Gamma\) an abelian group? Draw the multiplication table for \(\Gamma\).
Denote by \(GL(n)\) the set of \(n\times n\) invertible matrices. Then \(GL(n)\) is a group with matrix multiplication being the group operation. Recall that matrix multiplication is associative, that is, if \(\bs{A},\bs{B},\bs{C}\) are matrices then \(\bs{A}(\bs{B}\bs{C}) = (\bs{A}\bs{B})\bs{C}\), and thus property (i) is satisfied. The identity element of \(GL(n)\) is the \(n\times n\) identity matrix \(\bs{I}\) (the matrix with ones along the diagonal and all other entries are zero). By definition, each \(\bs{A}\in GL(n)\) has an inverse \(\bs{A}^{-1}\) and \(\bs{A}^{-1}\in GL(n)\) because \(\bs{A}^{-1}\) is itself invertible (its inverse is \(\bs{A}\)). Hence, \(GL(n)\) satisfies all the properties of a group. Note that matrix multiplication is not commutative and thus \(GL(n)\) is not an abelian group for \(n\geq 2\).
For our purposes, the most important group is the group of bijections on a finite set. Recall that bijections are one-to-one and onto mappings, and are therefore invertible. To be concrete, we will consider the finite set \(V=\{1,2,\ldots,n\}\) where \(n\in\mathbb{N}\) is fixed. A permutation on \(V\) is a bijection \(\sigma:V\rightarrow V\). The set of all permutations on the set \(V\) is called the symmetric group on \(V\), and it is usually denoted by \(S_n\). We now show that \(S_n\) is indeed a group. First of all, the candidate binary operation on \(S_n\) will be function composition. Recall that if \(\sigma_1\) and \(\sigma_2\) are functions from \(V\) to \(V\) then the composite function \(\sigma_1\circ\sigma_2\) is the new function defined by \((\sigma_1\circ\sigma_2)(k) = \sigma_1 (\sigma_2(k))\) for each \(k\in V\). Given \(\sigma_1,\sigma_2\in S_n\) the composite function \(\sigma_1\circ\sigma_2\) is also a bijection on \(V\) and thus \(\sigma_1\circ\sigma_2\in S_n\). Hence, function composition is a binary operation on \(S_n\). Now we verify that each property of a group is satisfied for \(S_n\) with group operation being function composition:
Function composition is associative; if \(\sigma_1,\sigma_2,\sigma_3\in S_n\) then \((\sigma_1\circ\sigma_2) \circ \sigma_3 = \sigma_1\circ (\sigma_2\circ\sigma_3)\). Associativity of function composition is not only true for bijections but for any functions.
The identity element of \(S_n\) is the identity permutation \(\text{id}:V\rightarrow V\) defined as \(\text{id}(k) = k\) for every \(k\in V\). In other words, the function \(\text{id}\) fixes each element of \(V\). For any \(\sigma\in S_n\) we have that \((\sigma\circ\text{id})(k) = \sigma(\text{id}(k)) = \sigma(k)\) and so \(\sigma\circ \text{id} = \sigma\). Similarly, \((\text{id}\circ \sigma)(k) = \text{id}(\sigma(k)) = \sigma(k)\), and therefore \(\text{id}\circ\sigma = \sigma\). Hence, the identity permutation is the identity element of \(S_n\).
Lastly, by definition of \(S_n\) each \(\sigma\in S_n\) has an inverse \(\sigma^{-1}\) and because \(\sigma^{-1}\) is itself invertible (its inverse is \(\sigma\)) then \(\sigma^{-1}\in S_n\). By definition of an inverse function, we have that \(\sigma\circ\sigma^{-1} = \text{id}\) and \(\sigma^{-1}\circ\sigma = \text{id}\).
If \(V=\{1,2,\ldots, n\}\) then the number of permutations on \(V\) is \(n!\), and therefore \(|S_n|=n!\). As \(n\) increases, \(S_n\) becomes a very big set. The group \(S_n\) is perhaps one of the most important groups in all of mathematics (\href{https://en.wikipedia.org/wiki/Permutation_group}{Permutation group}).
A permutation \(\sigma:V\rightarrow V\) can be represented as array in the following way:
\[
\sigma = \begin{pmatrix} 1 & 2 & 3 & \cdots & n\\ \sigma(1) & \sigma(2) & \sigma(3) & \cdots & \sigma(n)\end{pmatrix}.
\]
The array representation indicates that the number \(i\in V\) is mapped to \(\sigma(i)\in V\). For example, if \(V=\{1,2,3,4\}\) and \(\sigma\) is the permutation \(\sigma(1)=3, \sigma(2) = 4, \sigma(3) = 1\), and \(\sigma(4)=2\) then the array representation of \(\sigma\) is
\[
\sigma = \begin{pmatrix} 1 & 2 & 3 & 4\\ 3 & 4 & 1 & 2\end{pmatrix}.
\]
The array representation indicates that a permutation \(\sigma\) is a rearrangement of the ordered list \((1,2,3,\ldots,n)\) into the list \((\sigma(1), \sigma(2),\ldots,\sigma(n))\). Since \(\sigma\) is one-to-one and onto, every integer in \(\{1,2,\ldots,n\}\) will appear once and only once in the list \((\sigma(1), \sigma(2),\ldots,\sigma(n))\).
Let \(V=\{1,2,3\}\) so that \(|S_n| = 3! = 6\). Using array representations, write out all \(6\) permutations on \(V\).
Another more common way to represent a permutation is via its cycle decomposition. As an example, consider the permutation on \(n=8\) defined as
\[
\sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8\\
4 & 8 & 5 & 3 & 1 & 6 & 7 & 2\end{pmatrix}.
\]
Then \(\sigma(1) = 4\), and \(\sigma(4) = 3\), and \(\sigma(3) = 5\), and \(\sigma(5) = 1\) which is where we started. We then say that the sequence of integers \((1\; 4\; 3\; 5)\) is a cycle of \(\sigma\) because \(\sigma\) cycles through the list \((1,4,3,5)\) mapping one integer to the next until reaching the end of the list which is mapped to the first integer. Now take the lowest integer not in the cycle \((1\; 4\; 3\; 5)\), in this case it is \(2\). Then \(\sigma(2) = 8\) and \(\sigma(8)=2\) which is where we started. Hence \((2\; 8)\) is another cycle of \(\sigma\). Now select the next integer that does not appear in any of the previous cycles, in this case it is \(6\). Now \(\sigma(6) = 6\) and so \((6)\) is another cycle of \(\sigma\). Lastly, \(\sigma(7) = 7\). Hence, \(\sigma\) fixes the integers \(6\) and \(7\) and thus the cycles for these are both singleton cycles. The permutation \(\sigma\) can therefore be represented as the product of the cycles
\[
\sigma = (1\; 4\; 3\; 5)(2 \;8)(6)(7).
\]
This is called the cycle decomposition of \(\sigma\). From the cycle decomposition we can read directly what \(\sigma\) does to each integer. For example, to find \(\sigma(4)\) we simply find \(4\) in the cycle decomposition and pick out the integer to the right of \(4\), in this case \(\sigma(4)=3\). As another example, \(\sigma(5)=1\) because \(5\) is at the end of a cycle and so this means \(5\) is mapped to the beginning of the cycle, which is \(1\). The length of a cycle is the number of integers appearing in the cycle. Therefore, \((1\; 4\; 3\; 5)\) is a cycle of length 4, \((2\; 8)\) is a cycle of length 2, and \((6)\) and \((7)\) are cycles of length 1. By convention, cycles of length one are not displayed in the cycle decomposition of \(\sigma\). In this case, the cycle decomposition of \(\sigma\) would be written as \(\sigma=(1\;4\;3\;5)(2\;8)\) and it is understood that the remaining integers not displayed are fixed by \(\sigma\) (in this case 6 and 7).
Let \(n=10\) and let \(\sigma\in S_n\) be defined by
\[
\sigma = \begin{pmatrix}
1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\
3 & 6 & 1 & 8 & 5 & 9 & 2 & 10 & 7 & 4
\end{pmatrix}.
\]
Find the cycle decomposition of \(\sigma\) and determine the lengths of the cycles.
Suppose that \(\sigma\) is a permutation on \(n=9\) and it has the cycle decomposition
\[
\sigma = (1\;7\;9\;4)(2\;6\;5)
\]
Write the array representation of \(\sigma\).
Let \(\sigma_1, \sigma_2\in S_6\) have cycle decomposition \(\sigma_1=(1\;3)(2\;5\;6)\) and \(\sigma_2=(2\;3)(4\;5\;1)\). Find the array representation of the composition \(\sigma_1\circ\sigma_2\) and then write out the cycle decomposition of \(\sigma_1\circ \sigma_2\). Do the same for \(\sigma_2\circ\sigma_1\). Try writing the cycle decomposition of \(\sigma_1\circ\sigma_2\) and \(\sigma_2\circ\sigma_1\) directly using the cycle decompositions of \(\sigma_1\) and \(\sigma_2\) without first writing their array representations.
Let \(n=10\) and let \(\sigma\in S_n\) be defined by
\[
\sigma = \begin{pmatrix}
1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\
5 & 7 & 6 & 10 & 9 & 3 & 4 & 8 & 1 & 2
\end{pmatrix}.
\]
Write out the cycle decomposition of \(\sigma\) and then find the cycle decomposition of \(\sigma^{-1}\). Compare the cycle decompositions of \(\sigma\) and \(\sigma^{-1}\). Do you see how to quickly find the cycle decomposition of \(\sigma^{-1}\) once you know the cycle decomposition of \(\sigma\)?
By the order of a permutation \(\sigma\) we mean the least integer \(k\geq 1\) such that
\[
\sigma^k=\underbrace{\sigma\circ\sigma\circ\cdots\circ\sigma}_{k\text{-times}} = \text{id}.
\]
If the cycle decompsotion of \(\sigma\) has \(r\) cycles each having length \(k_1,k_2,\ldots,k_r\geq 2\) then the order of \(\sigma\) is the least common multiple (lcm) of \(k_1,k_2,\ldots,k_r\).
Let \(\sigma = (1\;5)(2\;3\;6\;4)\) be a permutation in \(S_6\). The length of the cycles of \(\sigma\) are \(k_1=2\) and \(k_2=4\). Hence, the order of \(\sigma\) is \(\text{lcm}(2,4) = 4\). Find \(\sigma^2, \sigma^3, \sigma^4\) and verify that \(\sigma^4\) is the identity permutation.
Let \(\Gamma\) be a group such that every element \(\sigma\in\Gamma\) has order \(k=2\). Prove that \(\Gamma\) is an abelian group, that is, that \(\sigma_1\sigma_2 =\sigma_2\sigma_1\) for all \(\sigma_1,\sigma_2\in \Gamma\).
Finally, a transposition is a permutation that fixes all but two elements. Hence, if \(\tau\) is a transposition then its cycle decomposition is of the form \(\tau=(a\; b)\) and thus \(\tau(a) = b\) and \(\tau(b) = a\) and \(\tau\) fixes all other integers. Clearly, the order of \(\tau\) is two. In particular, if \(\sigma=\tau_1\circ\tau_2\circ\cdots\circ\tau_r\) is a product of disjoint transpositions (by disjoint we mean that the cycles in all the \(\tau_i\)'s are mutually disjoint and by product we mean function composition because composition is the product operation in \(S_n\)) then \(\sigma\) is also of order two. For example, the permutation \(\sigma=(1\; 7)(2\; 5)(3\; 8)\) in \(S_9\) has order \(2\). The converse also holds; if \(\sigma\in S_n\) has order two then \(\sigma\) can be written as a product of disjoint transpositions.
Exercises
Write a Python function that takes as input a permutation represented as a list and returns the cycle decomposition of the permutation as a list of lists. Call your function cycleDecomposition. For example, consider the permutation
\[
\sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7\\2&4&1&3&7&6&5\end{pmatrix}.
\]
We can represent \(\sigma\) as a list as \(\sigma=[2,4,1,3,7,6,5]\). However, recall that Python uses zero-based indexing and thus as a Python list we have \(\sigma=[1,3,0,2,6,5,4]\). The cycle decomposition of \(\sigma\) as a list of lists is therefore \(\sigma = [[0,1,3,2], [4,6], [5]]\). Hence, your function would produce:
Apply your function to the following permutations (using zero-based indexing):
\begin{align*}
\sigma &= [2,0,1,5,7,10,11,4,8,9,3,6]\\
\sigma &= [2,6,7,8,1,3,11,4,9,10,0,5]\\
\sigma &= [13,7,0,8,18,2,17,9,1,3,14,15,12,5,16,11,6,10,4]
\end{align*}
To test your function further, the Python module itertools has a function called permutations that returns a generator that produces permutations of a given iterable such as a list or a string. Warning: Generating all permutations for even small values of \(n\) can take a long time; for this reason use \(n\leq 10\).
Graph isomorphisms
In this section, we study in detail what it means for two graphs to be ``equivalent'' but not necessarily equal. The basic idea is that since the essential structure of a graph is contained entirely in the make-up of the edge set, or how the vertices are connected, the vertex set can be seen as an arbitrary choice of labels for the vertices. If two graphs have the same edge structure then we will declare them to be equivalent even though the vertices might be distinct or differ by a rearrangement. For example, consider the two graphs \(G_1\) and \(G_2\) given by
\begin{align*}
V(G_1) &= \{v_1,v_2,v_3,v_4\} & V(G_2) &= \{x,y,z,w\}\\
E(G_1) &= \{v_1v_2,v_1v_3,v_2v_3,v_3v_4\} & E(G_2) &= \{zy, zw, yw, xw\}.
\end{align*}
It is clear that \(G_1\) and \(G_2\) are distinct graphs because \(V(G_1)\neq V(G_2)\). In each graph, there is one dominating vertex; in \(G_1\) it is \(v_3\) and in \(G_2\) it is \(w\). Each graph has one vertex with degree one; in \(G_1\) it is \(v_4\) and in \(G_2\) it is \(x\). In both graphs, the remaining two vertices are adjacent and each have the same degree. Hence, in both graphs the manner in which the vertices are connected is the same and the only feature that distinguishes the graphs are the actual names or labels of the vertices. Specifically, our analysis has shown that there exists a bijection between the vertices of \(G_1\) and \(G_2\) that shows that these graphs are structurally equivalent (but not equal). To be more precise, the bijection \(\sigma:V(G_1)\rightarrow V(G_2)\) defined by \(\sigma(v_3) = w\), \(\sigma(v_4)=x\), \(\sigma(v_2)=y\), and \(\sigma(v_1) = z\) leaves the adjacency property of vertices invariant. Let us now be more rigorous with the definition of equivalent graphs.
The graph \(G_1=(V_1,E_1)\) is isomorphic to the graph \(G_2=(V_2,E_2)\) if there exists a bijection \(\sigma:V_1\rightarrow V_2\) such that if \(\set{u,v}\) is an edge in \(G_1\) then \(\set{\sigma(u),\sigma(v)}\) is an edge in \(G_2\) and if \(\set{u, v}\) is not an edge in \(G_1\) then \(\set{\sigma(u),\sigma(v)}\) is not an edge in \(G_2\). In this case, we say that \(\sigma\) is an isomorphism from \(G_1\) to \(G_2\) and we write \(G_1\cong G_2\).
In other words, \(\sigma\) is an isomorphism from \(G_1\) to \(G_2\) if \(\sigma\) maps an edge in \(G_1\) to an edge in \(G_2\) and maps a non-edge in \(G_1\) to a non-edge in \(G_2\), in other words
\[
E_2 = \sigma(E_1) := \set{ \{\sigma(u), \sigma(v)\} \; |\; \{u,v\} \in E_1 }.
\]
Before we proceed, we note that if \(G_1\) is isomorphic to \(G_2\) then \(G_2\) is isomorphic to \(G_1\) (why>. Hence, we can without ambiguity say that \(G_1\) and \(G_2\) are isomorphic. Clearly, if \(G_1\cong G_2\) then necessarily \(|V_1|=|V_2|\) since there is no bijection between sets of distinct cardinality. Moreover, if \(\sigma\) is a bijection, the condition that \(\sigma(E_1) = E_2\) implies that also \(|E_1|=|E_2|\). A mathematical way to say this is that the order and size of a graph are invariants, that is, quantities (or objects, sub-structures, etc.) that are preserved by an isomorphism. Later on we will identify further invariants of graphs.
Verify that the graphs \(G_1=(V_1,E_1)\) and \(G_2=(V_2,E_2)\) shown in Figure 1.4 are distinct. Then prove that \(G_1\) and \(G_2\) are isomorphic. To do this, you need to explicitly find a bijection \(\sigma:V\rightarrow V\) that satisfies the definition of a graph isomorphism. Here \(V=V_1=V_2=\{v_1,v_2,v_3,v_4,v_5\}\). Once you have an isomorphism \(\sigma\), pick any non-edge in \(G_1\) and show that it is mapped under \(\sigma\) to a non-edge in \(G_2\).
Are these graphs isomorphic?
Given two graphs \(G_1=(V_1,E_1)\) and \(G_2=(V_2,E_2)\), if \(|V_1| \neq |V_2|\) then as discussed above \(G_1\) and \(G_2\) cannot be isomorphic. Hence, if \(G_1\) and \(G_2\) are graphs with \(n=|V_1|=|V_2|\), then when investigating whether \(G_1\) and \(G_2\) are isomorphic we can without loss of generality rename the vertex sets of \(G_1\) and \(G_2\) so that the new relabelled graphs both have the same vertex set. It is convenient to let the common vertex set be \(V=\{v_1,v_2,\ldots,v_n\}\) or even \(V=\{1,2,,\ldots,n\} \).
Consider the graphs \(G_1=(V,E_1)\) and \(G_2=(V,E_2)\) where \(V=\{1,2,3,4\}\) and
\begin{align*}
E_1 &= \{\{1,2\},\{1,3\},\{2,3\},\{3,4\}\}\\
E_2 &= \{\{3,4\}, \{2,4\}, \{2,3\}, \{1,2\} \}.
\end{align*}
Consider the permutation \(\sigma = (1\; 4)(2\; 3)\) (this is the cycle decomposition). Verify that \(\sigma\) is an isomorphism from \(G_1\) to \(G_2\) and thus \(G_1\cong G_2\). Draw both graphs to see what is happening.
Suppose that \(\sigma:V(G_1)\rightarrow V(G_2)\) is an isomorphism from \(G_1\) to \(G_2\). Prove that for every vertex \(v \in V(G_1)\) it holds that \(\deg(v) = \deg(\sigma(v))\). In other words, an isomorphism must preserve the degree of each vertex. Conclude that the degree sequence of isomorphic graphs are equal. In other words, the degree sequence of a graph is an invariant.
Consider the graphs \(G_1=(V,E_1)\) and \(G_2=(V,E_2)\) with vertex set \(V=\set{1,2,\ldots,6}\) and edge sets
\begin{align*}
{E}_1 &= \{\{3,5\}, \{4,6\}, \{2,6\}, \{1,5\}, \{3,6\}, \{1,4\},\{3,4\}\}\\
{E}_2 &= \{\{1,2\}, \{1,5\}, \{2,4\}, \{5,6\}, \{6,4\}, \{1,3\},\{5,2\}\}.
\end{align*}
The degree sequences of \(G_1\) and \(G_2\) are \(d(G_1)=d(G_2) = (3,3,3,2,2,1)\). Thus, there is a possibility that \({G}_1\) and \({G}_2\) are isomorphic. With the help of a drawing of \({G}_1\) and \({G}_2\), conclude that \(G_1\cong G_2\) and determine an isomorphism from \({G}_1\) to \({G}_2\).
Suppose that \(\sigma:V(G_1)\rightarrow V(G_2)\) is an isomorphism of the graphs \(G_1\) and \(G_2\). If \((w_0, w_1, \ldots, w_r)\) is a path in \(G_1\) then \((\sigma(w_0), \sigma(w_1), \ldots, \sigma(w_r))\) is a path in \(G_2\).
First of all, since \(\sigma\) is a bijection, all vertices in the list \[(\sigma(w_0), \sigma(w_1), \ldots, \sigma(w_r))\] are distinct. Since \(\{w_{i-1}, w_i\}\in E(G_1)\) and \(\sigma\) is an isomorphism then
\[
\{\sigma(w_{i-1}) , \sigma(w_i)\} \in E(G_2),
\]
for \(i=1,\ldots,r\). Thus, \((\sigma(w_0), \sigma(w_1), \ldots, \sigma(w_r))\) is a path in \(G_2\).
Recall that the distance between vertices \(u\) and \(v\) in a graph \(G\), denoted by \(d_G(u,v)\), is the length of a shortest path in \(G\) from \(u\) to \(v\), and if there is no path from \(u\) to \(v\) then \(d(u,v)\) does not exist. Prove that if \(\sigma:V(G_1)\rightarrow V(G_2)\) is an isomorphism from \(G_1\) to \(G_2\) then \(d_{G_1}(u,v) = d_{G_2}(\sigma(u), \sigma(v))\) for all vertices \(u,v\in V(G_1)\).
Prove that if \(G_1\) and \(G_2\) are isomorphic then their complements \(\overline{G}_1\) and \(\overline{G}_2\) are isomorphic.
Suppose that \(G_1\cong G_2\). Prove that \(G_1\) is connected if and only if \(G_2\) is connected.
Given two graphs \(G_1=(V,E_1)\) and \(G_2=(V,E_2)\), how do we decide if they are isomorphic? Well, first of all it must hold that \(|E_1|=|E_2|\) otherwise the graphs are not isomorphic. If we select a specific permutation \(\sigma:V\rightarrow V\) and if it is true that \(\set{u,v}\in E_1\) if and only if \(\set{\sigma(u),\sigma(v)}\in E_2\), for all \(u, v \in V\), then \(G_1\) and \(G_2\) are isomorphic. Hence, it is computationally easy to verify whether or not a specific permutation is an isomorphism from one graph to the other. If a specific permutation \(\sigma\) is not an isomorphism from \(G_1\) to \(G_2\), then we proceed by choosing another permutation \(\tilde{\sigma}\) and perform the same test and if \(\tilde{\sigma}\) is not an isomorphism then we proceed to another permutation, etc. In principle, we would have to perform an exhaustive test through all \(n!\) permutations on \(V\) to decide if \(G_1\) and \(G_2\) are isomorphic. This brute-force search is computationally intractable when \(n\) is large; in fact it is already computationally non-trivial even when say \(n\approx 20\). In general, the existence of an efficient algorithm that decides whether two given graphs \(G_1\) and \(G_2\) are isomorphic is still unknown and is a long-standing unsolved problem in mathematics and computer science (\href{https://en.wikipedia.org/wiki/Graph_isomorphism_problem}{Graph isomorphism problem}).
You may have already noticed that being isomorphic defines an equivalence relation on the set of all graphs with \(n\) vertices. To be concrete, let \(V=\{1,2,\ldots,n\}\) and let \(\mathcal{G}_n\) be the set of all graphs with vertex set \(V\), that is,
\[
\mathcal{G}_n = \set{ (V,E) \; |\; E\subset\binom{V}{2} }.
\]
Recall that the cardinality of \(\mathcal{G}_n\) is \(|\mathcal{G}_n| = 2^{\binom{n}{2}}\). We say that two graphs \(G_1\) and \(G_2\) are equivalent if \(G_1\) and \(G_2\) are isomorphic. To see that this is indeed an equivalence relation, we first note that \(G\cong G\) by taking the identity permutation since \(\text{id}(E) = E\) (this shows reflexivity); next if \(G_1\cong G_2\) and \(\sigma\) is the isomorphism such that \(\sigma(E_1) = E_2\) then \(G_2\cong G_1\) with isomorphism \(\sigma^{-1}\) since \(\sigma^{-1}(E_2) = E_1\) (this shows symmetry); and finally to show transitivity if \(G_1\cong G_2\) with isomorphism \(\sigma\) and \(G_2\cong G_3\) with isomorphism \(\rho\) then \(\rho\circ \sigma\) is an isomorphism from \(G_1\) to \(G_3\) since \((\rho\circ\sigma)(E_1) = \rho(\sigma(E_1)) = \rho(E_2) = E_3\). Hence, for fixed \(V=\{1,2,\ldots,n\}\), we can partition the set of all graphs \(\mathcal{G}_n\) into equivalences classes.
Let \(G=(V,E)\) be a graph on the vertex set \(V=\{1,2,\ldots,n\}\). The isomorphism class of \(G\) is the set of all graphs with vertex set \(V\) that are isomorphic to \(G\). We will denote the isomorphism class of \(G\) by \([G]\). Explicitly,
\[
[G] = \big\{ (V,\sigma(E)) \; |\; \sigma \in S_n \big\}.
\]
The number of distinct isomorphism classes on \(V\) will be denoted by \(\zeta(n)\).
An isomorphism class can be thought of as a graph with unlabelled vertices. The following exercise illustrates this point.
Let \(n=4\). If we draw all \(2^{\binom{n}{2}}=64\) graphs on the vertex set \(V=\{v_1,v_2,v_3,v_4\}\), and remove the labels of the vertices, then each graph will look like one of those shown in Figure 1.5. Therefore, there are \(\zeta(4) = 11\) isomorphism classes for \(n=4\). Alternatively, we say that there are \(\zeta(4)=11\) non-isomorphic graphs on \(n=4\) vertices.
The graph isomorphism classes for \(n=4\)
Given a graph \(G=(V,E)\), one can generate by brute-force the individual members of the isomorphism class \([G]\) by computing \(\sigma(E)\) for every permutation \(\sigma \in S_n\). One expects \([G]\) to contain \(n!\) graphs (one for each element of \(S_n\)) and in many (most) cases this is indeed true. In general, however, the isomorphism class \([G]\) will contain less than \(n!\) graphs as the next example shows.
Consider the graph \(G=(V,E)\) where \(V=\{1,2,3,4\}\) and
\[
E=\{\{1,2\},\{1,3\},\{2,3\},\{3,4\}\}.
\]
There are a total of \(4! = 24\) permutations in \(S_4\). Any graph \(\tilde{G}\) isomorphic to \(G\) is of the form \(\tilde{G}=(V, \sigma(E))\) for some permutation \(\sigma\in S_n\). Consider the permutations \(\sigma_1=(1\; 4)(2\; 3)\) and \(\sigma_2 = (1\; 3\; 2\; 4)\), both in their cycle decomposition. Clearly, these permutations are distinct. Verify however that \(\sigma_1(E) = \sigma_2(E)\) and thus \(\sigma_1\) and \(\sigma_2\) generate the same graph isomorphic to \(G\). This shows that the set \([G]\) contains less than \(4!\) graphs. In fact, one can show that in this case \([G]\) contains only \(12\) graphs.
Let \(G_1=(V,E_1)\) be the graph shown in Figure 1.6. Let \(\sigma_1=(1\; 3)(2\; 4)(5\;6)\) and let \(\sigma_2=(1\;2)(3\;4)\). Verify that \(\sigma_1(E_1) = E_1\) and \(\sigma_2(E_1) = E_1\). Hence, the equivalence class of \(G_1\) contains fewer than \(6!\) graphs. On the other hand, for the graph \(G_2=(V,E_2)\), one can verify that for all non-identity permutations \(\sigma\in S_6\), it holds that \(\sigma(E_2) \neq E_2\).
Two graphs on \(n=6\) vertices
The previous examples illustrate that for some graphs there are permutations that preserve the adjacency property of vertices. This leads us to the following definition.
An automorphism of a graph \(G=(V,E)\) is an isomorphism of \(G\) onto itself, that is, a bijection \(\sigma:V\rightarrow V\) such that \(\{u,v\}\) is an edge in \(G\) if and only if \(\{\sigma(u),\sigma(v)\}\) is an edge in \(G\). In other words, if \(\sigma(E)=E\). The set of all automorphisms of a graph \(G\) is called the automorphism group of \(G\), and will be denoted by \(\aut(G)\).
As the name suggests, the automorphism group is a group, and more specifically, it is a subgroup of the symmetric group. For any graph \(G\), the identity permutation is an automorphism of \(G\). If, however, \(G\) has only the identity permutation as an automorphism then we say that \(G\) is asymmetric otherwise we say that \(G\) is symmetric. We verified that the graph \(G_1\) in Figure 1.6 is a symmetric graph while graph \(G_2\) in the same figure is asymmetric. For small graphs, automorphisms may be found by identifying the ``geometric symmetries'' from a visual representation of the graph. In general, however, this approach is futile for finding automorphisms for large graphs and serves only to illustrate the idea of an automorphism.
Find at least two automorphisms for each graph in Figure 1.7. You will first need to label the vertices of the graph.
Finding automorphisms using a visual representation for small graphs
The complete graph \(K_n\) on the vertex set \(V=\{1,2,\ldots,n\}\) has every permutation on \(V\) as an automorphism. Thus, \(\aut(K_n)=S_n\). Verify this for \(K_3\).
When \(n\) is very small, a typical graph will have an automorphism other than the identity permutation, that is, when \(n\) is small a typical graph will have at least one symmetry. In fact, an exhaustive search reveals that it is not until \(n=6\) that asymmetric graphs appear. It is natural to ask what the trend is as \(n\rightarrow\infty\). As before, let \(\zeta(n)\) denote the number of graph isomorphism classes on \(n\) vertices. We have seen that some graphs have a non-trivial automorphism group and therefore there are isomorphism classes that contain fewer than \(n!\) graphs. Therefore,
\[
2^{\binom{n}{2}} \lt n! \zeta(n)
\]
from which it follows that
\[
\frac{ 2^{\binom{n}{2}} }{n!} \lt \zeta(n).
\]
It can be shown \cite{CG-RG:01} that in fact \(\zeta(n)\) asymptotically converges to \(\frac{ 2^{\binom{n}{2}} }{n!}\) (see Figure 1.8), that is,
\[
\lim_{n\rightarrow\infty} \frac{\zeta(n)} { \frac{ 2^{\binom{n}{2}} }{n!} }= 1.
\]
From this fact one can deduce that as \(n\rightarrow\infty\), the proportion of graphs that are asymmetric tends to one. These facts were proved by P. Erd{\"o}s and A. R{\'e}yni \cite{PE-AR:63} and summarized below.
For each \(n\in\mathbb{N}\), let \(a(n)\) be the number of asymmetric non-isomorphic graphs on \(n\) vertices. Then
\[
\lim_{n\rightarrow\infty} \frac{a(n)}{\zeta(n)} = 1,
\]
that is, the proportion of graphs that are asymmetric for each \(n\) tends to 1 as \(n\rightarrow\infty\).
Another way of saying this is that almost all graphs are asymmetric (\href{https://en.wikipedia.org/wiki/Asymmetric_graph}{Asymmetric graphs}). Although symmetry in graphs is mathematically rare, many real-world graph models have many symmetries.
The ratio \(\frac{\zeta(n)n!} { 2^{\binom{n}{2}}}\) for \(n\in\{1,2,\ldots,40\}\). The values of \(\zeta(n)\) were obtained from the On-Line Encyclopedia of Integer Sequences \href{https://oeis.org/A000088}{https://oeis.org/A000088}.
Exercises
A subset of vertices \(W\subset V(G)\) of a graph \(G\) is called a clique if all vertices in \(W\) are mutually adjacent. In other words, \(W\) is a clique if the induced subgraph \(G[W]\) is a complete graph. Prove that if \(\sigma\) is an isomorphism from \(G\) to \(H\) then if \(W\) is a clique in \(G\) then \(\sigma(W)\) is a clique in \(H\).
Prove that if \(G_1\cong G_2\) then \(\text{diam}(G_1) = \text{diam}(G_2)\).
Two vertices \(u, v \in V(G)\) are said to be twin vertices if \(N(u)\backslash\hspace{-0.3em}\set{v} = N(v)\backslash\hspace{-0.3em}\set{u}\). In other words, \(u\) and \(v\) are twins if they have the same neighbors (other than possibly themselves). Prove that \(u\) and \(v\) are twin vertices if and only if the transposition that permutes \(u\) and \(v\), and fixes all other vertices, is an automorphism of \(G\).
Are these graphs isomorphic? If not explain why, and if yes then provide an isomorphism.
We know that the degree sequence of a graph is an isomorphism invariant.
Show by example that two graphs with the same degree sequence need not be isomorphic. Your graphs should be non-regular graphs.
Do the same as in part (a) but now the two graphs must be regular.
For each case, explain why they are non-isomorphic. Your explanation should not be ``because the pictures of the graph look different''.
Are these graphs isomorphic? If not explain why, and if yes then provide an isomorphism.
The eccentricity of a vertex \(v\in V(G)\), denoted by \(\ecc_G(v)\), is the maximum distance from \(v\) to any other vertex in \(G\). In other words,
\[
\ecc_G(v) = \max_{u\in V} d(v, u).
\]
The radius of a graph \(G\), denoted by \(\text{rad}(G)\), is the minimum eccentricity among all vertices of \(G\). The center of \(G\) is the subset of vertices \(v\) such that \(\ecc_G(v) = \text{rad}(G)\). Suppose that \(\sigma\) is an isomorphism from \(G_1\) to \(G_2\). Prove that
\(\ecc_{G_2}(\sigma(v)) = \ecc_{G_1}(v)\) for every \(v\in V(G_1)\),
\(\text{rad}(G_1) = \text{rad}(G_2)\), and
the center of \(G_1\) is mapped onto the center of \(G_2\) under \(\sigma\).
Prove that the number of connected components in a graph is an invariant. In other words, if \(G\) has connected components \(G_1, G_2, \ldots, G_k\), and \(H\) has connected components \(H_1, H_2, \ldots, H_\ell\) then if \(G\cong H\) then \(k=\ell\). To get you started, prove the following: Suppose that \(\sigma:V(G)\rightarrow V(H)\) is an isomorphism from \(G\) to \(H\). If \(G_i\) is a connected component of \(G\) then the graph in \(H\) induced by the vertices \(\sigma(V(G_i))\) is a connected component in \(H\).
Special graphs and graph operations
In this section, we present a small catalog of graphs that appear frequently in graph theory and also present some standard operations on graphs.
We have already discussed the complete graph on \(n\) vertices, denoted by \(K_n\), which is the graph where all vertices are mutually adjacent. The complement of the complete graph is the empty graph, denoted by \(E_n = \overline{K_n}\).
Fix a vertex set \(V=\set{v_1,v_2,\ldots,v_n}\). The path graph on \(V\), denoted by \(P_n\), is the graph with edge set
\[
E(P_n) = \set{v_1v_2,v_2v_3,\ldots, v_{n-1}v_n}.
\]
Hence, \(P_n\) is a path of length \(n-1\) from \(v_1\) to \(v_n\). The cycle graph on \(V\), denoted by \(C_n\), is the graph with edge set
\[
E(C_n) = \set{v_1v_2, v_2v_3, v_3v_4,\ldots,v_{n-1}v_n, v_nv_1} = E(P_n) \cup \{v_1,v_n\}.
\]
Hence, \(C_n\) can be obtained by connecting the end-vertices of \(P_n\). In Figure 1.9, we illustrate \(P_2, P_3, P_4\), and \(C_3, C_4, C_5\).
Some path and cycle graphs
A graph \(G\) is called self-complementary if \(G\) is isomorphic to its complement.
Verify that \(P_4\) is self-complementary.
Prove that if \(G\) is self-complementary then \(|E(G)| = \frac{\binom{n}{2}}{2}\), and thus \(G\) has half the number of edges of the complete graph.
Deduce that \(n\equiv 0\) or \(n\equiv 1 \pmod 4\).
A graph \(G\) is called bipartite if there exists two non-empty disjoint subsets \(X\) and \(Y\) of \(V(G)\) such that \(X\cup Y = V(G)\) and every edge in \(G\) has one end-vertex in \(X\) and the other in \(Y\). The sets \(X\) and \(Y\) are called the parts of the bipartition \(\set{X,Y}\). Bipartite graphs are usually drawn with the vertices from \(X\) on one side and the vertices from \(Y\) on the other side. An example of a bipartite graph, drawn in two different ways, is shown in Figure 1.10.
A bipartite graph
Suppose that \(G\) is a connected bipartite graph. Prove that \(G\) has a unique bipartition. In other words, prove that if \(\{X, Y\}\) and \(\{A,B\}\) are bipartitions of \(G\) then \(\{A,B\} = \{X,Y\}\). Give an example of a disconnected bipartite graph that does not have a unique bipartition.
The complete bipartite graph of regularity \((n_1, n_2)\), denoted by \(K_{n_1, n_2}\), is a bipartite graph with parts \(X\) and \(Y\) such that \(n_1 = |X|\) and \(n_2 = |Y|\) and every vertex in \(X\) is adjacent to all vertices in \(Y\) (and hence all vertices in \(Y\) are adjacent to \(X\)). Figure 1.11 illustrates \(K_{2,3}\) and \(K_{1,4}\).
The complete bipartite graphs \(K_{2,3}\) and \(K_{1,4}\).
We now give a characterization of bipartite graphs.
A graph \(G\) is bipartite if and only if it does not contain cycles of odd length.
Suppose first that \(G\) is bipartite with parts \(X\) and \(Y\), and let \(\gamma=(w_0, w_1, \ldots, w_k)\) be a cycle in \(G\) of length \(k\), and thus \(w_0=w_k\). Assume without loss of generality that \(w_0 \in X\). Since \(G\) is bipartite, \(w_i \in X\) for all even \(i\) and \(w_j \in Y\) for all odd \(j\). Since \(w_k=w_0 \in X\), it follows that \(k\) is even and thus the cycle \(\gamma\) has even length.
Now we prove the converse statement. The statement is trivial if \(|V(G)| \leq 2\) so suppose that \(n\geq 3\). We can assume that \(G\) is connected, otherwise we apply the forthcoming arguments to each connected component of \(G\). Let \(v\in V(G)\) be an arbitrary but fixed vertex and define
\[
X = \set{x \in V(G)\;|\; d(v, x)\text{ is even}}
\]
and let \(Y = V(G)\backslash\hspace{-0.3em} X\). Hence, \(Y\) contains vertices whose distance to \(v\) is odd. It is clear that \(X\) and \(Y\) are disjoint. Since \(G\) is connected, \(X\cup Y= V(G)\). Assume that \(G\) is not bipartite. Then at least one of \(X\) or \(Y\) contains two adjacent vertices. Suppose without loss of generality that \(X\) contains two vertices \(a\) and \(b\) that are adjacent. Then neither \(a\) nor \(b\) equals \(v\) by definition of \(X\). Let \(\gamma_1=(a_0,a_1,a_2,\ldots,a_{2k})\) be a path of minimum length from \(v\) to \(a\) and let \(\gamma_2=(b_0,b_1,b_2,\ldots,b_{2j})\) be a path of minimum length from \(v\) to \(b\). Both paths \(\gamma_1\) and \(\gamma_2\) contain \(v=a_0=b_0\) as a common vertex. In general, if \(\gamma_1\) and \(\gamma_2\) contain a common vertex \(v'\) then \(v'=a_i= b_i\) for some \(i\). Indeed, if \(v'=a_i\) and \(v'=b_\ell\) for say \(i \lt \ell\) then there exists a path from \(v\) to \(b\) that has length less than \(\gamma_2\) which is a contradiction. Let \(i\) be the largest integer such that \(a_i = b_i\). Then \((a_i, a_{i+1}, \ldots, a_{2k}, b_{2j}, b_{2j-1}, \ldots, b_i)\) is a cycle of length \((2k-i) + (2j-i) + 1\), which is odd. Hence, we have proved that if \(G\) is not bipartite then \(G\) has a cycle of odd length. Thus, if \(G\) has no cycles of odd length then \(G\) is bipartite.
Label the cycle graph \(C_6\) and find a bipartition for it.
Given two graphs \(G\) and \(H\) with disjoint vertex sets, we define the union of \(G\) and \(H\), denoted by \(G\oplus H\), as the graph with vertex set \(V(G)\cup V(H)\) and edge set \(E(G)\cup E(H)\). The join of \(G\) and \(H\), denoted by \(G\vee H\), is the graph obtained from \(G\oplus H\) by connecting every vertex in \(G\) to every vertex in \(H\). Explicitly,
\[
E(G\vee H) = E(G) \cup E(H) \cup \set{\set{v,w}\;|\; v\in V(G),\; w\in V(H)}.
\]
It is not hard to show that \(\oplus\) and \(\vee\) are commutative and associative operations, in other words,
\begin{align*}
G_1 \oplus G_2 &= G_2 \oplus G_1 & (G_1\oplus G_2)\oplus G_3 &= G_1\oplus (G_2\oplus G_3)\\
G_1 \vee G_2 &= G_2 \vee G_1 & (G_1\vee G_2)\vee G_3 &= G_1\vee (G_2\vee G_3).
\end{align*}
for all graphs \(G_1,G_2,G_3\). It is clear that \(G_1\oplus G_2\) is a disconnected graph while \(G_1\vee G_2\) is connected.
Suppose that \(G\) is disconnected and has components \(G_1, G_2,\) \(\ldots, G_k\). Then \(G = G_1 \oplus G_2 \oplus \cdots \oplus G_k\).
Suppose that \(G=G_1\vee G_2\). Prove that \(\diam(G)\leq 2\). What if \(\diam(G) = 1\)?
Recall that \(K_{|X|,|Y|}\) is the bipartite graph with parts \(X\) and \(Y\) such that every vertex in \(X\) is adjacent to every vertex in \(Y\). Prove that \(K_{|X|, |Y|} = E_{|X|} \vee E_{|Y|}\), where recall that \(E_n\) is the empty graph on \(n\) vertices.
Given a graph \(G\) and \(v\in V(G)\), we denote by \(G-v\) the graph obtained from \(G\) by removing the vertex \(v\) and all edges incident with \(v\). More generally, for \(S\subset V(G)\), the graph \(G-S\) is the graph obtained from \(G\) by removing all vertices \(S\) and all edges incident with a vertex in \(S\). Formally,
\[
G - S = G[S^c]
\]
where \(S^c = V(G)\backslash\hspace{-0.3em} S\). Similarly, if \(e\in E(G)\) then \(G-e\) is the graph obtained from \(G\) by removing the edge \(e\), and more generally, for \(\Omega\subset E(G)\), the graph \(G-\Omega\) is obtained from \(G\) by removing all edges in \(\Omega\), in other words, \(E(G - \Omega) = E(G)\backslash\hspace{-0.3em}\Omega\).
Let \(G\) be a connected graph. A vertex \(v\in V(G)\) is called a cut vertex if \(G-v\) is disconnected. More generally, a subset \(S\) of vertices is called a vertex cut set if \(G-S\) is disconnected. The minimum cardinality over all vertex cut sets is called the connectivity of \(G\) and denoted by \(\kappa(G)\). If \(G\) is disconnected we define \(\kappa(G) = 0\) and \(\kappa(K_n) = n-1\) for \(n\geq 1\). Similarly, an edge \(e\) is called a bridge if \(G-e\) is disconnected. A subset \(\Omega\subset E(G)\) of edges is called an edge cut set if \(G-\Omega\) is disconnected. The minimum cardinality over all edge cut sets is called the edge connectivity of \(G\) and denoted by \(e(G)\).
For any connected graph \(G\) we have \(\kappa(G)\leq e(G)\leq \delta(G)\).
If \(v\) is a vertex with \(\deg(v)=\delta(G)\) then removing all edges incident with \(v\) leaves \(v\) isolated and therefore \(G\) is disconnected. Hence, \(e(G)\leq \delta(G)\). The other inequality is left as an exercise.
The girth of a graph \(G\), denoted by \(g(G)\), is the length of the shortest cycle in \(G\). Prove that \(g(G) \leq 2\diam(G)+1\) for any graph \(G\) with at least one cycle. Assume \(G\) is connected.
Exercises
Is the graph given below bipartite? If yes, find a bipartition for it.
Consider the complete bipartite graph \(K_{n_1, n_2}\).
Find the number of edges of \(K_{n_1, n_2}\) in terms of \(n_1\) and \(n_2\).
Is there a complete bipartite graph with \(n=11\) vertices and 25 edges? Explain.
Is there a complete bipartite graph with \(n=11\) vertices and 24 edges? Explain.
Draw the graph \(K_{1,n-1}\) for \(n=5\), \(n=7\), and \(n=9\). What celestial objects do these graphs resemble?
For each \(n\geq 4\), let \(W_n = C_{n-1} \vee K_1\). Draw \(W_n\) for \(n\in \{4,5,9,12\}\). What name would you give these graphs?
Draw the graph \(K_1\vee (E_2\oplus C_3)\).
Let \(G_1\) and \(G_2\) be graph.
Prove that if \(G_1\vee G_2\) is a regular graph then both \(G_1\) and \(G_2\) are regular.
Suppose that \(G_1\) is \(k_1\)-regular, with \(n_1\) vertices, and \(G_2\) is \(k_2\)-regular, with \(n_2\) vertices. Under what conditions on \(k_1, k_2, n_1\), and \(n_2\) is \(G_1\vee G_2\) a regular graph? Give a proof of your condition.
Give an example of regular graphs \(G_1\) and \(G_2\) such that \(G_1\vee G_2\) is not regular.
Consider the following recursively defined sequence of graphs:
\begin{align*}
G_1 &= K_1 \\
G_2 &= G_1 \vee K_1\\
G_3 &= G_2 \oplus K_1\\
G_4 &= G_3 \vee K_1\\
G_5 &= G_4 \oplus K_1
\end{align*}
and in general \(G_{k} = G_{k-1} \oplus K_1\) if \(k\geq 3\) is odd and \(G_{k} = G_{k-1} \vee K_1\) if \(k\geq 2\) is even.
Draw \(G_8\) and label the vertices so that the vertex added at step \(j\) is labelled \(v_{j}\).
Prove by induction that if \(k\) is even then
\[
d(G_k) = \left(k-1, k-2, \ldots, \tfrac{k}{2}, \tfrac{k}{2}, \tfrac{k}{2}-1, \ldots, 2, 1\right).
\]
In other words, the degree sequence has only one repeated value, namely \(\frac{k}{2}\).
Let \(G\) be a graph with \(\delta(G)\geq k\).
Prove that \(G\) has a path of length at least \(k\).
Prove that if \(k\geq 2\) then \(G\) has a cycle of length at least \(k+1\).
Prove that if \(\delta(G) \geq \frac{n}{2} + 1\) then adjacent vertices have a common neighbor, that is, for every \(\{u, v\} \in E(G)\) there exists \(w\in V(G)\) such that \(\{u, w\}\in E(G)\) and \(\{v, w\}\in E(G)\).
The complete multipartite graph of regularity \((n_1,n_2,\) \(\ldots,n_k)\), denoted by \(K_{n_1,n_2,\ldots,n_k}\), is the graph
\[
K_{n_1,n_2,\ldots,n_k} = E_{n_1}\vee E_{n_2}\vee \cdots \vee E_{n_k}.
\]
In other words, there is a partition \(X_1, X_2,\ldots, X_k\) of the vertex set \(V\) such that for each distinct \(X_i\) and \(X_j\), each vertex of \(X_i\) is adjacent to every vertex of \(X_j\). Find the order and size of \(K_{n_1,n_2,\ldots, n_k}\) in terms of \(n_1,n_2,\ldots,n_k\).
Prove that the center of a complete bipartite graph \(K_{n_1, n_2}\), with \(n_1, n_2 \geq 2\), is the entire vertex set. (See Exercise 1.24 for the definition of the center of a graph.)
Trees
We begin at the beginning.
A graph \(G\) is called a tree if it is connected and does not contain any cycles. A forest is the union of trees.
It follows by definition and Theorem 1.5.1 that a tree is a bipartite graph. By definition, \(K_1\) is a tree, and the only trees on \(n=2\) and \(n=3\) vertices are \(P_2\) and \(P_3\), respectively. Some trees are shown in Figure 1.12.
Some tree graphs
There are 2 trees on \(n=4\) vertices and 3 trees on \(n=5\) vertices. Draw them.
Let \(G\) be a connected graph. Then \(G\) is a tree if and only if there is a unique path between any two given vertices.
We first prove that if \(G\) is a tree then for any distinct vertices \(u\) and \(v\) there is only one path from \(u\) to \(v\). We prove the contrapositive. Suppose that there are two distinct paths \(\gamma_1=(x_0,x_1,\ldots,x_k)\) and \(\gamma_2=(y_0,y_1,\ldots,y_\ell)\) from \(u\) to \(v\), and thus \(u=x_0=y_0\) and \(x_k=y_\ell = v\). Since the paths are distinct, there is a minimal \(i\geq 1\) such that \(x_i \neq y_i\) and \(x_{i-1} = y_{i-1}\). Since the paths have at least one vertex in common after \(u\) (namely \(v\)), there is a minimal \(j \gt i\) such that \(x_j = y_m\) for some \(m\leq \ell\). Hence, \(\tilde{\gamma}=(x_{i-1}, x_i, \ldots, x_j, y_{m-1},y_{m-2},\ldots, y_i, y_{i-1})\) is a cycle in \(G\), and thus \(G\) is not a tree.
Now suppose that \(G\) is not a tree and let \(\gamma=(u,w_1,w_2,\ldots,w_k,u)\) be a cycle in \(G\). Then for \(1\leq i \lt k\), \(\gamma_1=(u,w_1,\ldots,w_i)\) and \(\gamma_2=(u,w_k,w_{k-1},\ldots,w_i)\) are two paths in \(G\) from \(u\) to \(w_i\). Hence, if in \(G\) there is only one path between any two given vertices then \(G\) has no cycles, that is, \(G\) is a tree.
A vertex \(v\) of a tree \(G\) is called a leaf or a pendant vertex if \(\deg(v) = 1\). If \(G\) is a tree and \(\deg(v) =1\) then \(G-v\) is connected and contains no cycles. Therefore, \(G-v\) is a tree whenever \(\deg(v)=1\). Before we continue, we need the following more-or-less obvious fact.
If \(G\) is a connected graph of order \(n\geq 3\) then there exists \(v\in V(G)\) such that \(\deg(v)\geq 2\).
If \(\deg(v) = 1\) for all \(v\in V(G)\) then \(G\) is the disjoint union of copies of \(P_2\) and thus \(G\) is not connected.
We now describe what happens to a tree when we remove a non-leaf.
If \(G\) is a tree with \(n\geq 3\) vertices then \(G-v\) is a forest for any \(v\in V(G)\) having \(\deg(v)\geq 2\). In fact, the number of components of \(G-v\) is \(\deg(v)\).
Let \(v\in V(G)\) be such that \(\deg(v)\geq 2\) and consider \(G-v\). Let \(x, y\) be neighbors of \(v\) in \(G\). If \(G-v\) is connected, then there exists a path in \(G-v\) from \(x\) to \(y\), say \(\gamma=(x, w_1, w_2, \ldots, w_{k-1}, y)\). Then \(\tilde{\gamma} = (x,w_1,w_2,\ldots,w_{k-1},y,v,x)\) is a cycle in \(G\) which is a contradiction since \(G\) is a tree. Hence, \(G-v\) is disconnected. Our proof also shows that each neighbor of \(v\) is contained in a distinct component of \(G-v\), and hence \(G-v\) contains at least \(\deg(v)\) components. It is clear, however, that \(G-v\) can have no more than \(\deg(v)\) components for if \(H\) is a component of \(G-v\) that does not contain any of the neighbors of \(v\) in \(G\) then \(G\) contains \(H\) as a connected component which contradicts the connectivity of \(G\). Finally, if any component of \(G-v\) contains a cycle then clearly so does \(G\) which is a contradiction. Hence, \(G-v\) is a forest containing \(\deg(v)\) trees.
Every tree with \(n\geq 2\) vertices contains at least two leaves.
The proof is by strong induction on \(n\). For \(n=2\) and \(n=3\), the only trees are \(P_2\) and \(P_3\), respectively, and both contain two leaves. Now assume that the claim is true for all trees having no more than \(n\geq 2\) vertices and let \(G\) be a tree of order \(n+1\). Since \(n+1\geq 3\), Lemma 1.6.3 applies and thus \(G\) has a vertex \(v\) with \(\deg(v)\geq 2\). If \(v\) is adjacent to two or more leaves then we are done. If \(v\) is adjacent to one leaf, say \(x\), then \(G-x\) is a tree of order \(n\) and therefore it has at least two leaves, say \(y\) and \(z\). This implies that \(G\) has at least two of \(x,y,z\) as leaves. If \(v\) is not adjacent to any leaves, then \(G-v\) contains at least two components \(G_1\) and \(G_2\) each containing at least \(2\) vertices. By the induction hypothesis, \(G_1\) contains at least two leaves, say \(x_1\) and \(y_1\), and \(G_2\) contains at least two leaves \(x_2\) and \(y_2\). Hence, \(G\) contains at least two of \(x_1,y_1,x_2,y_2\) as leaves.
The following gives a characterization of trees in terms of the number of edges.
Suppose that \(G\) is a connected graph with \(n\) vertices. Then \(G\) is a tree if and only if \(G\) has \(n-1\) edges.
We first prove that if \(G\) is a tree with \(n\) vertices then it has \(n-1\) edges. The case \(n=1\) is trivial. Assume by induction that every tree with \(n\) vertices contains \(n-1\) edges. Let \(G\) be a tree with \(n+1\) vertices. Let \(v\) be a leaf of \(G\). Then \(G-v\) is a tree with \(n\) vertices and therefore by the induction hypothesis has \(n-1\) edges. Since \(G\) and \(G-v\) differ only by one edge, \(G\) has \((n-1)+1 = n\) edges.
Now we prove that every connected graph with \(n\) vertices and \(n-1\) edges is a tree. The case \(n=1\) is trivial. Assume by induction that every connected graph with \(n\) vertices and \(n-1\) edges is a tree. Let \(G\) be a connected graph with \(n+1\) vertices and \(n\) edges. We claim that there is at least one vertex \(v\) with \(\deg(v)=1\). If not, then \(\sum_{i=1}^{n+1} \deg(v_i) \geq 2(n+1)\), while by the Handshaking lemma we have \(\sum_{i=1}^{n+1}\deg(v_i) = 2n\), which is a contradiction. Let then \(v\in V(G)\) be such that \(\deg(v) = 1\). Then \(G-v\) is a connected graph with \(n\) vertices and \(n-1\) edges. By induction, \(G-v\) is a tree. Since \(\deg(v) = 1\), it is clear that \(G\) is also a tree.
We obtain the following corollary.
If \(G\) is a forest of order \(n\) containing \(k\) components then \(G\) has \(n-k\) edges.
We now describes what happens in a tree when an edge is removed.
Let \(G\) be a tree. Then every edge in \(G\) is a bridge. Moreover, \(G-e\) is a forest with two components for any edge \(e \in E(G)\).
Let \(G\) be a connected graph. Assume that no edge of \(G\) is a bridge. Hence, if \(e=\{u,v\}\) is an edge in \(G\) then \(G-e\) is connected. Thus, there exists a path in \(G-e\) from \(u\) to \(v\). Adding the edge \(e\) at the end of this path creates a cycle in \(G\), and hence \(G\) is not a tree. Hence, if \(G\) is a tree then every edge is a bridge.
To prove the second claim, let \(G_1,G_2,\ldots,G_k\) be the components of \(G-e\). Since \(G\) is a tree, each component \(G_i\) contains no cycles and therefore \(G_i\) is a tree. Hence, the total number of edges in \(G-e\) is \(n-k\). On the other hand, \(G\) has \(n-1\) edges and therefore \(G-e\) has \(n-2\) edges. This implies \(k=2\).
Exercises
Is there a forest with \(k=2\) components having \(n=15\) vertices and \(m=12\) edges? If no, explain why, and if yes provide one. Repeat with \(k=3\).
Suppose that \(G\) is a tree. Prove that if \(e\) is not an edge of \(G\) then \(G+e\) has a cycle.
Let \(a\) be the average degree of a tree \(G\) with \(n\) vertices. Find an expression for \(n\) in terms of \(a\).
Let \(G\) be a tree. Prove that if \(d(u,v) = \diam(G)\) then \(u\) and \(v\) are both leaves. Recall that \(\diam(G)\) is the length of the longest path in \(G\).
Let \(G\) be a tree.
Prove that \(G\) has at least \(\Delta(G)\) leaves.\\ { (Hint: Theorem 1.6.4 and Proposition 1.6.5 might be useful here.)}
Give an example of a tree that has exactly \(\Delta(G)\) leaves.
Let \(G\) be a tree of order \(n\geq 2\). Prove that the number of leaves in \(G\) is
\[
2 + \sum_{\deg(v_i)\geq 3} (\deg(v_i) - 2).
\]
