Graphs | An Introduction to Algebraic Graph Theory

What is a graph?

Before we give the definition of a graph, we introduce the following useful notation. For any set we denote by the set of all two-element subsets of , that is, If is finite and contains elements then the number of elements of is For instance, if then and the number of elements of is . We are now ready to define a graph.

A graph consists of two sets and where is some subset of . The set is called the vertex set of and is called the edge set of . In this case we write .

Let be a graph. The elements of are called the vertices of and the elements of are called the edges of . We will frequently use the notation and to denote the vertex set and edge set, respectively, of . If is a finite set, then 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 and form an edge in the graph if and are ``related''. The condition for being ``related'' might be that and are friends in a social network, or and are subway stations that are directly linked by a train, or and 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 by drawing a point on the 2D plane for each vertex and then connecting vertices and with a line if and only if . As an example, a visual representation of the graph with vertex set and edge set 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 and where .

figures/small-graph.svg — Visual representation of the graph with vertex set and edge set

Consider the graph shown in Figure 1.2. Based on this graphical representation of , what is and ?

figures/large-graph.svg — For this graph , what is and ?

Let be the graph with vertex set and edge set What is the edge set and how many edges does have? Draw a visual representation of .

Check-out the Wiki page on \href{https://en.wikipedia.org/wiki/Graph_theory}{Graph theory}.

Exercises

Let

be the graph with vertex set

and edge set

Write out the edge set

and draw the graph

. How many edges does

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

be the set of

-dimensional binary vectors. In other words, an element of

is of the form

where

is either zero or one. Let

be the graph with edge set

consisting of edges formed by two binary vectors that differ at only a single entry. For example, if

and

then

is an edge of

since

and

differ only in the third entry, whereas if

and

then

is note an edge of

. Do the following:

Explicitly write out the vertex set . How many vertices are there?
Explicitly write out the edge set . How many edges are there?
Make a visual representation of in the 2D plane. (Do not read part (d) yet!)
Now make a visual representation of in a 3D coordinate system by drawing each vertex as a point in .

Consider the following list

and let

. Let

be the graph such that

if and only if the numbers

and

appear in reverse order in

. For example,

because

appears before

and so are in correct order, whereas

because

appears before

and so are in reverse order. Write out the edge set

and draw a visual representation of

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

is the cardinality of the vertex set

and the size of

is the cardinality of the edge set. Usually, we use the variables

and

to denote the order and size of

, respectively. Given two vertices

, we say that

and

are adjacent or neighbors if

. In this case, we will write

to denote adjacency and, whenever it is convenient to do so, we will denote the 2-element set

by simply

. Given an edge

, we will simply say that

and

are the vertices of the edge

. If

we say that

is incident with

and that

is incident with

. The neighborhood of

, denoted by

, is the set of all vertices adjacent to

, in other words

The degree of a vertex

, denoted by

, is the cardinality of

, that is, the number of neighbors of

. It is clear that

for all

. A vertex

with

is called a dominating vertex and if

then

is called an isolated vertex. The maximum/minimum degree of a graph

is the maximum/minimum degree among all vertices of

. The maximum degree of

is denoted by

and the minimum degree is denoted by

, in other words

and

It is clear that

. The degree sequence of a graph

, denoted by

, is the sequence of the vertex degrees of

listed in decreasing order. Hence, if

then the degree sequence of

is of the form

where

Consider again the graph

in Figure 1.2.

What is the order and size of ?
Find , , and , and .
Find and .
Find the degree sequence .
Find and compare it with .

The last part of the previous example is known as the Handshaking Lemma.

For any graph

it holds that

Consequently, in any graph the number of vertices with odd degree is even.

The degree of

counts the number of edges incident with

. Since each edge is incident with exactly two vertices, the sum

counts each edge twice, and therefore

. It follows then that the number of vertices

with odd degree

is even.

Another property of the degree sequence is the following.

In any graph

there are at least two vertices with equal degree.

Let

be any graph of order

with degree sequence

We consider two mutually exclusive cases. In the first case, if

then

. Hence,

for every

, and then by the pigeon-hole principle there is at least two degrees that are equal. On the other hand, if

then

for every

, 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

be a finite set with cardinality

. How many distinct graphs are there with vertex set

? Let us first consider two extreme cases. The empty graph on

, which we will denote by

, is the graph whose edge set is the empty set, that is,

. A visual representation of the empty graph consists of

points in the plane with no edges among the vertices. At the other extreme, the complete graph, which we will denote by

, is the graph in which each vertex is adjacent to all other vertices. Hence, in the complete graph

, every possible edge is present. The total number of possible edges in a graph with

vertices is

. For example, if

then the set of all 2-element subsets of

and in this case

, which is the cardinality of

. Now, recall that by definition of a graph, the edge set is a subset of

. Hence, the total number of distinct graphs with vertex set

is equal to the number of subsets of

. The number of subsets of a set with

elements is

. Applying this to the set

we conclude that the number of graphs with vertex set

is therefore

where

is a set with

elements then the number of distinct graphs with vertex set

How many graphs are there with vertex set

? Draw all of them and group them by the number of edges in the graph.

Let

be a finite set with cardinality

. How many graphs are there on

that have exactly

edges? Note that necessarily

. Use your result to obtain a formula for

The complement of a graph

is the graph

with the same vertex set as

and whose edge set consists of all edges not present in

. In other words,

. It follows then that

Let

be the graph with

and

What is

? Draw both

and

is a graph of order

and

then what is

? Here we are using the notation

to denote the degree of

in the graph

and

the degree of

. In general, what is

in terms of

and

A graph

is said to be

-regular if every vertex in

has degree

. If

-regular then clearly

. Conversely, given any graph

then

is a regular graph.

Prove that if

-regular then

is also regular. What is the degree of each vertex in

Draw a

-regular graph on

vertices.

Is there a

-regular graph on

vertices if

and

? To answer this question, prove that if

is a

-regular graph on

vertices then

must be even. Hint: Use the Handshaking lemma.

A graph

is said to be a subgraph of

and

. For any subset of vertices

, the subgraph induced by

, denoted by

, is the subgraph of

with vertex set

and edge set

In other words, the subgraph

contains all edges of

whose end-vertices are in

. 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

with

and edge set

is a subgraph of

. However, it is not an induced subgraph. The subgraph of

induced by the vertices

(that is, the graph

has edge set

A subgraph

is called a path in

if we can order the vertices of

, say

, such that

for

. We also say that

is a path from the vertex

and that the length of the path

. As an example,

is a path of length six in the graph in Figure 1.2. A graph

is said to be connected if for any distinct vertices

there exists a path from

, and is called disconnected otherwise. A connected component of a graph

is an induced subgraph

such that

is connected and

is not a proper subgraph of a connected subgraph of

. From these definitions, it is straightforward to show that a graph

is connected if and only if it contains only one connected component.

Draw a graph on

vertices with

edges having 3 connected components.

Prove that if

is disconnected then

is connected. Give an example of a connected graph

such that

is also connected. Hint: There is one for

and several for

Having defined the length of a path, we define the distance between vertices.

The distance between vertices

is the length of a shortest path from

(or equivalently from

). We denote the distance between

and

, and if the graph

is understood simply by

. If there is no path in

from

then

is not defined.

Let

be a connected subgraph of the connected graph

and let

and

be vertices of

. Prove that

Lastly, the diameter of a connected graph

, denoted by

, is the maximum distance among all the vertices in

, in other words

is a connected subgraph of a connected graph

, what is the relationship between

and

? To answer this question consider the following.

Give an example of and such that .
Give an example of and such that .
Give an example of and such that .
Suppose that for all vertices . Prove that .

Exercises

How many graphs are there with vertex set

? How many of these have

edges?

Let

be a graph with

and

. Show that

What statistical measure of the vertex degrees is

Let

be the set of all Hollywood actors and let

be the graph where

if and only if

and

have appeared in the same Hollywood film.

For , what does represent?
If is such that , what can we say about the actor and the film(s) has appeared in?
If is such that , what can we say about the actor and the film(s) has appeared in?
What does represent?

has degree sequence

, what is the degree sequence of

Draw a graph with degree sequence

For each case, decide whether or not a graph can have the given degree sequence. Justify your answers.

Draw the complement of the graph

shown below:

For the graph shown in Figure 1.3 with vertex set

, decide if the given subgraph

is induced. Explain your answer.

figures/induced-subgraph.svg — Graph for Exercises 1.12 and 1.13

For the graph

in Figure 1.3, determine a path from

. What is the length of the path? Do the same for vertices

. What is

How many edges in a graph guarantee that it is connected? To answer this question, show the following.

Let be a graph with vertices and edges. Show that if then is connected. Hint: Try this for small .
Show that for each , there exists a graph with edges that is disconnected.
Conclude that is the least number of edges that guarantee that is connected.
Give an example of a connected graph with fewer than edges.

Show by example that if

is connected then

can be disconnected.

Prove that if

then

is a connected graph, where as usual

. Prove also that

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

but since these are usually the letters used for graphs, we will use instead the symbol

to denote a generic group. Let us recall the definition of a group.

A group is a set

and a binary operation defined on

, denoted by

, that satisfies the following:

For all it holds that (associativity)
There is an element such that and for every . The element is called the identity element.
For each there exists an element such that and . Usually, is denoted instead by so that , and is called an inverse of .

In many cases, the group operation

is a sort of product operation in which case the product

is denoted simply as

. Sometimes, however, the group operation is a sort of addition operation and so in that case

would be denoted by

. The essential feature, however, is that

is a binary operation that satisfies the listed properties (i)-(iii). Before we give examples of groups, we give the following definition.

A group

with group operation

is said to be an abelian group if the group operation is commutative, that is, if

for every

The integers

with the operation of addition forms a group. Indeed, addition is an associative operation; if

then

. The identity element of

is zero because

for every

. Lastly, for each

its inverse under addition is

, and since

it follows that every

has an inverse in

. Hence,

with operation

is a group. Since addition of integers is commutative, the group

is an abelian group.

The integers

with the operation of multiplication is not a group. What property of a group does

not satisfy when the operation is multiplication?

Consider the finite set

where

satisfies

. Then

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

, that is, whenever we take two elements in

and multiply them we obtain an element back in

. The identity element is the number

. Lastly, every element in

has an inverse that is in

. For example, the inverse of

because

. As another example, the inverse of

is itself because

. Is

an abelian group? Draw the multiplication table for

Denote by

the set of

invertible matrices. Then

is a group with matrix multiplication being the group operation. Recall that matrix multiplication is associative, that is, if

are matrices then

, and thus property (i) is satisfied. The identity element of

is the

identity matrix

(the matrix with ones along the diagonal and all other entries are zero). By definition, each

has an inverse

and

because

is itself invertible (its inverse is

). Hence,

satisfies all the properties of a group. Note that matrix multiplication is not commutative and thus

is not an abelian group for

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

where

is fixed. A permutation on

is a bijection

. The set of all permutations on the set

is called the symmetric group on , and it is usually denoted by

. We now show that

is indeed a group. First of all, the candidate binary operation on

will be function composition. Recall that if

and

are functions from

then the composite function

is the new function defined by

for each

. Given

the composite function

is also a bijection on

and thus

. Hence, function composition is a binary operation on

. Now we verify that each property of a group is satisfied for

with group operation being function composition:

Function composition is associative; if then . Associativity of function composition is not only true for bijections but for any functions.
The identity element of is the identity permutation defined as for every . In other words, the function fixes each element of . For any we have that and so . Similarly, , and therefore . Hence, the identity permutation is the identity element of .
Lastly, by definition of each has an inverse and because is itself invertible (its inverse is ) then . By definition of an inverse function, we have that and .

then the number of permutations on

, and therefore

. As

increases,

becomes a very big set. The group

is perhaps one of the most important groups in all of mathematics (\href{https://en.wikipedia.org/wiki/Permutation_group}{Permutation group}). A permutation

can be represented as array in the following way:

The array representation indicates that the number

is mapped to

. For example, if

and

is the permutation

, and

then the array representation of

The array representation indicates that a permutation

is a rearrangement of the ordered list

into the list

. Since

is one-to-one and onto, every integer in

will appear once and only once in the list

Let

so that

. Using array representations, write out all

permutations on

Another more common way to represent a permutation is via its cycle decomposition. As an example, consider the permutation on

defined as

Then

, and

which is where we started. We then say that the sequence of integers

is a cycle of

because

cycles through the list

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

, in this case it is

. Then

and

which is where we started. Hence

is another cycle of

. Now select the next integer that does not appear in any of the previous cycles, in this case it is

. Now

and so

is another cycle of

. Lastly,

. Hence,

fixes the integers

and

and thus the cycles for these are both singleton cycles. The permutation

can therefore be represented as the product of the cycles

This is called the cycle decomposition of

. From the cycle decomposition we can read directly what

does to each integer. For example, to find

we simply find

in the cycle decomposition and pick out the integer to the right of

, in this case

. As another example,

because

is at the end of a cycle and so this means

is mapped to the beginning of the cycle, which is

. The length of a cycle is the number of integers appearing in the cycle. Therefore,

is a cycle of length 4,

is a cycle of length 2, and

and

are cycles of length 1. By convention, cycles of length one are not displayed in the cycle decomposition of

. In this case, the cycle decomposition of

would be written as

and it is understood that the remaining integers not displayed are fixed by

(in this case 6 and 7).

Let

and let

be defined by

Find the cycle decomposition of

and determine the lengths of the cycles.

Suppose that

is a permutation on

and it has the cycle decomposition

Write the array representation of

Let

have cycle decomposition

and

. Find the array representation of the composition

and then write out the cycle decomposition of

. Do the same for

. Try writing the cycle decomposition of

and

directly using the cycle decompositions of

and

without first writing their array representations.

Let

and let

be defined by

Write out the cycle decomposition of

and then find the cycle decomposition of

. Compare the cycle decompositions of

and

. Do you see how to quickly find the cycle decomposition of

once you know the cycle decomposition of

By the order of a permutation

we mean the least integer

such that

If the cycle decompsotion of

has

cycles each having length

then the order of

is the least common multiple (lcm) of

Let

be a permutation in

. The length of the cycles of

are

and

. Hence, the order of

. Find

and verify that

is the identity permutation.

Let

be a group such that every element

has order

. Prove that

is an abelian group, that is, that

for all

Finally, a transposition is a permutation that fixes all but two elements. Hence, if

is a transposition then its cycle decomposition is of the form

and thus

and

fixes all other integers. Clearly, the order of

is two. In particular, if

is a product of disjoint transpositions (by disjoint we mean that the cycles in all the

's are mutually disjoint and by product we mean function composition because composition is the product operation in

) then

is also of order two. For example, the permutation

has order

. The converse also holds; if

has order two then

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

We can represent

as a list as

. However, recall that Python uses zero-based indexing and thus as a Python list we have

. The cycle decomposition of

as a list of lists is therefore

. Hence, your function would produce:

    cycleDecomposition([1,3,0,2,6,5,4]) 
         	[[0,1,3,2], [4,6], [5]]

Apply your function to the following permutations (using zero-based indexing):

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

can take a long time; for this reason use

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

and

given by

It is clear that

and

are distinct graphs because

. In each graph, there is one dominating vertex; in

it is

and in

it is

. Each graph has one vertex with degree one; in

it is

and in

it is

. 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

and

that shows that these graphs are structurally equivalent (but not equal). To be more precise, the bijection

defined by

, and

leaves the adjacency property of vertices invariant. Let us now be more rigorous with the definition of equivalent graphs.

The graph

is isomorphic to the graph

if there exists a bijection

such that if

is an edge in

then

is an edge in

and if

is not an edge in

then

is not an edge in

. In this case, we say that

is an isomorphism from

and we write

In other words,

is an isomorphism from

maps an edge in

to an edge in

and maps a non-edge in

to a non-edge in

, in other words

Before we proceed, we note that if

is isomorphic to

then

is isomorphic to

(why>. Hence, we can without ambiguity say that

and

are isomorphic. Clearly, if

then necessarily

since there is no bijection between sets of distinct cardinality. Moreover, if

is a bijection, the condition that

implies that also

. 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

and

shown in Figure 1.4 are distinct. Then prove that

and

are isomorphic. To do this, you need to explicitly find a bijection

that satisfies the definition of a graph isomorphism. Here

. Once you have an isomorphism

, pick any non-edge in

and show that it is mapped under

to a non-edge in

figures/are-graphs-isomorphic.svg — Are these graphs isomorphic?

Given two graphs

and

, if

then as discussed above

and

cannot be isomorphic. Hence, if

and

are graphs with

, then when investigating whether

and

are isomorphic we can without loss of generality rename the vertex sets of

and

so that the new relabelled graphs both have the same vertex set. It is convenient to let the common vertex set be

or even

Consider the graphs

and

where

and

Consider the permutation

(this is the cycle decomposition). Verify that

is an isomorphism from

and thus

. Draw both graphs to see what is happening.

Suppose that

is an isomorphism from

. Prove that for every vertex

it holds that

. 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

and

with vertex set

and edge sets

The degree sequences of

and

are

. Thus, there is a possibility that

and

are isomorphic. With the help of a drawing of

and

, conclude that

and determine an isomorphism from

Suppose that

is an isomorphism of the graphs

and

. If

is a path in

then

is a path in

First of all, since

is a bijection, all vertices in the list

are distinct. Since

and

is an isomorphism then

for

. Thus,

is a path in

Recall that the distance between vertices

and

in a graph

, denoted by

, is the length of a shortest path in

from

, and if there is no path from

then

does not exist. Prove that if

is an isomorphism from

then

for all vertices

Prove that if

and

are isomorphic then their complements

and

are isomorphic.

Suppose that

. Prove that

is connected if and only if

is connected.

Given two graphs

and

, how do we decide if they are isomorphic? Well, first of all it must hold that

otherwise the graphs are not isomorphic. If we select a specific permutation

and if it is true that

if and only if

, for all

, then

and

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

is not an isomorphism from

, then we proceed by choosing another permutation

and perform the same test and if

is not an isomorphism then we proceed to another permutation, etc. In principle, we would have to perform an exhaustive test through all

permutations on

to decide if

and

are isomorphic. This brute-force search is computationally intractable when

is large; in fact it is already computationally non-trivial even when say

. In general, the existence of an efficient algorithm that decides whether two given graphs

and

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

vertices. To be concrete, let

and let

be the set of all graphs with vertex set

, that is,

Recall that the cardinality of

. We say that two graphs

and

are equivalent if

and

are isomorphic. To see that this is indeed an equivalence relation, we first note that

by taking the identity permutation since

(this shows reflexivity); next if

and

is the isomorphism such that

then

with isomorphism

since

(this shows symmetry); and finally to show transitivity if

with isomorphism

and

with isomorphism

then

is an isomorphism from

since

. Hence, for fixed

, we can partition the set of all graphs

into equivalences classes.

Let

be a graph on the vertex set

. The isomorphism class of

is the set of all graphs with vertex set

that are isomorphic to

. We will denote the isomorphism class of

. Explicitly,

The number of distinct isomorphism classes on

will be denoted by

An isomorphism class can be thought of as a graph with unlabelled vertices. The following exercise illustrates this point.

Let

. If we draw all

graphs on the vertex set

, and remove the labels of the vertices, then each graph will look like one of those shown in Figure 1.5. Therefore, there are

isomorphism classes for

. Alternatively, we say that there are

non-isomorphic graphs on

vertices.

figures/isomorphism-classes-4.svg — The graph isomorphism classes for

Given a graph

, one can generate by brute-force the individual members of the isomorphism class

by computing

for every permutation

. One expects

to contain

graphs (one for each element of

) and in many (most) cases this is indeed true. In general, however, the isomorphism class

will contain less than

graphs as the next example shows.

Consider the graph

where

and

There are a total of

permutations in

. Any graph

isomorphic to

is of the form

for some permutation

. Consider the permutations

and

, both in their cycle decomposition. Clearly, these permutations are distinct. Verify however that

and thus

and

generate the same graph isomorphic to

. This shows that the set

contains less than

graphs. In fact, one can show that in this case

contains only

graphs.

Let

be the graph shown in Figure 1.6. Let

and let

. Verify that

and

. Hence, the equivalence class of

contains fewer than

graphs. On the other hand, for the graph

, one can verify that for all non-identity permutations

, it holds that

figures/automorphisms.svg — Two graphs on 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

is an isomorphism of

onto itself, that is, a bijection

such that

is an edge in

if and only if

is an edge in

. In other words, if

. The set of all automorphisms of a graph

is called the automorphism group of

, and will be denoted by

As the name suggests, the automorphism group is a group, and more specifically, it is a subgroup of the symmetric group. For any graph

, the identity permutation is an automorphism of

. If, however,

has only the identity permutation as an automorphism then we say that

is asymmetric otherwise we say that

is symmetric. We verified that the graph

in Figure 1.6 is a symmetric graph while graph

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.

figures/automorphisms-visually.svg — Finding automorphisms using a visual representation for small graphs

The complete graph

on the vertex set

has every permutation on

as an automorphism. Thus,

. Verify this for

When

is very small, a typical graph will have an automorphism other than the identity permutation, that is, when

is small a typical graph will have at least one symmetry. In fact, an exhaustive search reveals that it is not until

that asymmetric graphs appear. It is natural to ask what the trend is as

. As before, let

denote the number of graph isomorphism classes on

vertices. We have seen that some graphs have a non-trivial automorphism group and therefore there are isomorphism classes that contain fewer than

graphs. Therefore,

from which it follows that

It can be shown \cite{CG-RG:01} that in fact

asymptotically converges to

(see Figure 1.8), that is,

From this fact one can deduce that as

, 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

, let

be the number of asymmetric non-isomorphic graphs on

vertices. Then

that is, the proportion of graphs that are asymmetric for each

tends to 1 as

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.

figures/asymptotic-iso-classes.svg — The ratio for . The values of were obtained from the On-Line Encyclopedia of Integer Sequences \href{https://oeis.org/A000088}{https://oeis.org/A000088}.

Exercises

A subset of vertices

of a graph

is called a clique if all vertices in

are mutually adjacent. In other words,

is a clique if the induced subgraph

is a complete graph. Prove that if

is an isomorphism from

then if

is a clique in

then

is a clique in

Prove that if

then

Two vertices

are said to be twin vertices if

. In other words,

and

are twins if they have the same neighbors (other than possibly themselves). Prove that

and

are twin vertices if and only if the transposition that permutes

and

, and fixes all other vertices, is an automorphism of

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

, denoted by

, is the maximum distance from

to any other vertex in

. In other words,

The radius of a graph

, denoted by

, is the minimum eccentricity among all vertices of

. The center of

is the subset of vertices

such that

. Suppose that

is an isomorphism from

. Prove that

for every ,
, and
the center of is mapped onto the center of under .

Prove that the number of connected components in a graph is an invariant. In other words, if

has connected components

, and

has connected components

then if

then

. To get you started, prove the following: Suppose that

is an isomorphism from

. If

is a connected component of

then the graph in

induced by the vertices

is a connected component in

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

vertices, denoted by

, which is the graph where all vertices are mutually adjacent. The complement of the complete graph is the empty graph, denoted by

. Fix a vertex set

. The path graph on

, denoted by

, is the graph with edge set

Hence,

is a path of length

from

. The cycle graph on

, denoted by

, is the graph with edge set

Hence,

can be obtained by connecting the end-vertices of

. In Figure 1.9, we illustrate

, and

figures/path-cycles.svg — Some path and cycle graphs

A graph

is called self-complementary if

is isomorphic to its complement.

Verify that is self-complementary.
Prove that if is self-complementary then , and thus has half the number of edges of the complete graph.
Deduce that or .

A graph

is called bipartite if there exists two non-empty disjoint subsets

and

such that

and every edge in

has one end-vertex in

and the other in

. The sets

and

are called the parts of the bipartition

. Bipartite graphs are usually drawn with the vertices from

on one side and the vertices from

on the other side. An example of a bipartite graph, drawn in two different ways, is shown in Figure 1.10.

figures/bipartite-graph.svg — A bipartite graph

Suppose that

is a connected bipartite graph. Prove that

has a unique bipartition. In other words, prove that if

and

are bipartitions of

then

. Give an example of a disconnected bipartite graph that does not have a unique bipartition.

The complete bipartite graph of regularity

, denoted by

, is a bipartite graph with parts

and

such that

and

and every vertex in

is adjacent to all vertices in

(and hence all vertices in

are adjacent to

). Figure 1.11 illustrates

and

figures/complete-bipartite.svg — The complete bipartite graphs and .

We now give a characterization of bipartite graphs.

A graph

is bipartite if and only if it does not contain cycles of odd length.

Suppose first that

is bipartite with parts

and

, and let

be a cycle in

of length

, and thus

. Assume without loss of generality that

. Since

is bipartite,

for all even

and

for all odd

. Since

, it follows that

is even and thus the cycle

has even length. Now we prove the converse statement. The statement is trivial if

so suppose that

. We can assume that

is connected, otherwise we apply the forthcoming arguments to each connected component of

. Let

be an arbitrary but fixed vertex and define

and let

. Hence,

contains vertices whose distance to

is odd. It is clear that

and

are disjoint. Since

is connected,

. Assume that

is not bipartite. Then at least one of

contains two adjacent vertices. Suppose without loss of generality that

contains two vertices

and

that are adjacent. Then neither

nor

equals

by definition of

. Let

be a path of minimum length from

and let

be a path of minimum length from

. Both paths

and

contain

as a common vertex. In general, if

and

contain a common vertex

then

for some

. Indeed, if

and

for say

then there exists a path from

that has length less than

which is a contradiction. Let

be the largest integer such that

. Then

is a cycle of length

, which is odd. Hence, we have proved that if

is not bipartite then

has a cycle of odd length. Thus, if

has no cycles of odd length then

is bipartite.

Label the cycle graph

and find a bipartition for it.

Given two graphs

and

with disjoint vertex sets, we define the union of

and

, denoted by

, as the graph with vertex set

and edge set

. The join of

and

, denoted by

, is the graph obtained from

by connecting every vertex in

to every vertex in

. Explicitly,

It is not hard to show that

and

are commutative and associative operations, in other words,

for all graphs

. It is clear that

is a disconnected graph while

is connected.

Draw the graphs

and

Suppose that

is disconnected and has components

. Then

Suppose that

. Prove that

. What if

Recall that

is the bipartite graph with parts

and

such that every vertex in

is adjacent to every vertex in

. Prove that

, where recall that

is the empty graph on

vertices.

Given a graph

and

, we denote by

the graph obtained from

by removing the vertex

and all edges incident with

. More generally, for

, the graph

is the graph obtained from

by removing all vertices

and all edges incident with a vertex in

. Formally,

where

. Similarly, if

then

is the graph obtained from

by removing the edge

, and more generally, for

, the graph

is obtained from

by removing all edges in

, in other words,

. Let

be a connected graph. A vertex

is called a cut vertex if

is disconnected. More generally, a subset

of vertices is called a vertex cut set if

is disconnected. The minimum cardinality over all vertex cut sets is called the connectivity of

and denoted by

. If

is disconnected we define

and

for

. Similarly, an edge

is called a bridge if

is disconnected. A subset

of edges is called an edge cut set if

is disconnected. The minimum cardinality over all edge cut sets is called the edge connectivity of

and denoted by

For any connected graph

we have

is a vertex with

then removing all edges incident with

leaves

isolated and therefore

is disconnected. Hence,

. The other inequality is left as an exercise.

The girth of a graph

, denoted by

, is the length of the shortest cycle in

. Prove that

for any graph

with at least one cycle. Assume

is connected.

Exercises

Is the graph given below bipartite? If yes, find a bipartition for it.

Consider the complete bipartite graph

Find the number of edges of in terms of and .
Is there a complete bipartite graph with vertices and 25 edges? Explain.
Is there a complete bipartite graph with vertices and 24 edges? Explain.

Draw the graph

for

, and

. What celestial objects do these graphs resemble?

For each

, let

. Draw

for

. What name would you give these graphs?

Draw the graph

Let

and

be graph.

Prove that if is a regular graph then both and are regular.
Suppose that is -regular, with vertices, and is -regular, with vertices. Under what conditions on , and is a regular graph? Give a proof of your condition.
Give an example of regular graphs and such that is not regular.

Consider the following recursively defined sequence of graphs:

and in general

is odd and

is even.

Draw and label the vertices so that the vertex added at step is labelled .
Prove by induction that if is even then In other words, the degree sequence has only one repeated value, namely .

Let

be a graph with

Prove that has a path of length at least .
Prove that if then has a cycle of length at least .

Prove that if

then adjacent vertices have a common neighbor, that is, for every

there exists

such that

and

The complete multipartite graph of regularity

, denoted by

, is the graph

In other words, there is a partition

of the vertex set

such that for each distinct

and

, each vertex of

is adjacent to every vertex of

. Find the order and size of

in terms of

Prove that the center of a complete bipartite graph

, with

, 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

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,

is a tree, and the only trees on

and

vertices are

and

, respectively. Some trees are shown in Figure 1.12.

figures/some-trees.svg — Some tree graphs

There are 2 trees on

vertices and 3 trees on

vertices. Draw them.

Let

be a connected graph. Then

is a tree if and only if there is a unique path between any two given vertices.

We first prove that if

is a tree then for any distinct vertices

and

there is only one path from

. We prove the contrapositive. Suppose that there are two distinct paths

and

from

, and thus

and

. Since the paths are distinct, there is a minimal

such that

and

. Since the paths have at least one vertex in common after

(namely

), there is a minimal

such that

for some

. Hence,

is a cycle in

, and thus

is not a tree. Now suppose that

is not a tree and let

be a cycle in

. Then for

and

are two paths in

from

. Hence, if in

there is only one path between any two given vertices then

has no cycles, that is,

is a tree.

A vertex

of a tree

is called a leaf or a pendant vertex if

. If

is a tree and

then

is connected and contains no cycles. Therefore,

is a tree whenever

. Before we continue, we need the following more-or-less obvious fact.

is a connected graph of order

then there exists

such that

for all

then

is the disjoint union of copies of

and thus

is not connected.

We now describe what happens to a tree when we remove a non-leaf.

is a tree with

vertices then

is a forest for any

having

. In fact, the number of components of

Let

be such that

and consider

. Let

be neighbors of

. If

is connected, then there exists a path in

from

, say

. Then

is a cycle in

which is a contradiction since

is a tree. Hence,

is disconnected. Our proof also shows that each neighbor of

is contained in a distinct component of

, and hence

contains at least

components. It is clear, however, that

can have no more than

components for if

is a component of

that does not contain any of the neighbors of

then

contains

as a connected component which contradicts the connectivity of

. Finally, if any component of

contains a cycle then clearly so does

which is a contradiction. Hence,

is a forest containing

trees.

Every tree with

vertices contains at least two leaves.

The proof is by strong induction on

. For

and

, the only trees are

and

, respectively, and both contain two leaves. Now assume that the claim is true for all trees having no more than

vertices and let

be a tree of order

. Since

, Lemma 1.6.3 applies and thus

has a vertex

with

. If

is adjacent to two or more leaves then we are done. If

is adjacent to one leaf, say

, then

is a tree of order

and therefore it has at least two leaves, say

and

. This implies that

has at least two of

as leaves. If

is not adjacent to any leaves, then

contains at least two components

and

each containing at least

vertices. By the induction hypothesis,

contains at least two leaves, say

and

, and

contains at least two leaves

and

. Hence,

contains at least two of

as leaves.

The following gives a characterization of trees in terms of the number of edges.

Suppose that

is a connected graph with

vertices. Then

is a tree if and only if

has

edges.

We first prove that if

is a tree with

vertices then it has

edges. The case

is trivial. Assume by induction that every tree with

vertices contains

edges. Let

be a tree with

vertices. Let

be a leaf of

. Then

is a tree with

vertices and therefore by the induction hypothesis has

edges. Since

and

differ only by one edge,

has

edges. Now we prove that every connected graph with

vertices and

edges is a tree. The case

is trivial. Assume by induction that every connected graph with

vertices and

edges is a tree. Let

be a connected graph with

vertices and

edges. We claim that there is at least one vertex

with

. If not, then

, while by the Handshaking lemma we have

, which is a contradiction. Let then

be such that

. Then

is a connected graph with

vertices and

edges. By induction,

is a tree. Since

, it is clear that

is also a tree.

We obtain the following corollary.

is a forest of order

containing

components then

has

edges.

We now describes what happens in a tree when an edge is removed.

Let

be a tree. Then every edge in

is a bridge. Moreover,

is a forest with two components for any edge

Let

be a connected graph. Assume that no edge of

is a bridge. Hence, if

is an edge in

then

is connected. Thus, there exists a path in

from

. Adding the edge

at the end of this path creates a cycle in

, and hence

is not a tree. Hence, if

is a tree then every edge is a bridge. To prove the second claim, let

be the components of

. Since

is a tree, each component

contains no cycles and therefore

is a tree. Hence, the total number of edges in

. On the other hand,

has

edges and therefore

has

edges. This implies

Exercises

Is there a forest with

components having

vertices and

edges? If no, explain why, and if yes provide one. Repeat with

Suppose that

is a tree. Prove that if

is not an edge of

then

has a cycle.

Let

be the average degree of a tree

with

vertices. Find an expression for

in terms of

Let

be a tree. Prove that if

then

and

are both leaves. Recall that

is the length of the longest path in

Let

be a tree.

Prove that has at least leaves. { (Hint: Theorem 1.6.4 and Proposition 1.6.5 might be useful here.)}
Give an example of a tree that has exactly leaves.

Let

be a tree of order

. Prove that the number of leaves in