## Content

### Isomorphism

The fundamental issue raised by Question 10 and 11 is, when are two graphs the same? This leads us to a fundamental idea in graph theory: **isomorphism**. If two graphs are the same they are **isomorphic**. But how do you tell if two graphs are isomorphic? Well the low brow way is to move the vertices of one onto the vertices of another in such a way that the edges of both overlap the edges of the other. If this is possible, then the two graphs are said to be the same, isomorphic. If you can't then they're not. Have a look at Figure 4.

Showing the isomorphism of two graphs

The pictures show how to move the `closed red' vertices onto the `open red' ones so that the single edges of each graph line up. So the two graphs above are isomorphic. As a result the only graphs on three vertices are those with no edges, one edge, two edges and three edges. C in Question 11 is the correct answer.

So two graphs that are the same are said to be **isomorphic**. But we have to get highbrow and formalise this matter of isomorphism. The rough idea from the answers to Question 11, means that vertices of one graph go to vertices of the other. What's more it shows that the edges of one graph go to the edges of the other and non-edges go to non-edges. We can do this formalisation by a function from the vertices of one graph to the other that sends edges to edges and non-edges to non-edges. We hope the following formal definition is never asked for in an exam because there are far more important things to worry about. But here it is. Two graphs $G$ and $H$ are **isomorphic** if there is a one-to-one onto function (a bijection) $f$ between the vertices of $G$ and $H$ such that there is an edge between vertices $u$ and $v$ in $G$ if and only if there is an edge between the vertices $f(u) $and $f(v)$ in $H$. So first for every vertex of $G$ there is a corresponding vertex of $H$ and vice versa. And second, every edge of $G$ corresponds to an edge of $H$ and vice versa. That also means that non-edges go to non-edges. We write $G \cong H$ to indicate that $G$ and $H$ are isomorphic.

The isomorphism of graphs can trip you up, especially at the start. A particular graph can be drawn in more than one way so watch out for this. For instance, the apparently two different graphs shown in Figure 5 are actually isomorphic.

An isomorphic pair of graphs

Formally a bijection between vertices is $a \leftrightarrow u, b \leftrightarrow v, c \leftrightarrow x$, and $d \leftrightarrow w$ and between edges is $ab \leftrightarrow uv, ac \leftrightarrow ux, bd \leftrightarrow vw$. Using this bijection we can successfully `sit' the right graph on top of the left graph so that edges sit on the top of edges.

Questions

- Find another bijection between the two graphs in Figure 5.
- You may also have found a Z-shaped graph on four vertices. That is also isomorphic to the graph in Figure 5. Write out a bijection that will show this. Show that the edges and non-edges of one graph go to edges and non-edges of the other.

While we are thinking about isomorphism, it turns to be extremely difficult to tell when two graphs with even a reasonable number of edges are isomorphic. This difficulty is called the Isomorphism Problem for Graphs. See https://en.wikipedia.org/wiki/Graph_isomorphism _problem#State_of_the_art. Finding an isomorphism between two graphs is often very important.

- Have a look at the graphs $G$ and $H$ in Figure 6 and decide whether they are isomorphic or not.

Two potentially isomorphic graphs

In the answers we used an idea called `edge-in numbers'. This is something that a student might invent. Now 'edge-in numbers' is ugly, awkward, lengthy and misleading (they are the same as the edge-out numbers after all). So let's introduce a more standard name for these things. These numbers are usually called **degrees**. So the degrees of the vertices of $G$ are 1, 2, 3 and 2.

Questions

- Find the degrees of all the vertices of all the graphs on 4 vertices. Beside them put the number of edges that each graph has. Notice anything? Is there some relationship? Does that relationship work for graphs with 5 vertices? Does that work in general? Can you prove it?
- Will any sequence of numbers be the degrees of some graph? For instance, is it likely that there is a graph with degrees 1, 1, 1, 1, 1 or 1, 1, 1, 1, 1, 1?
- At a meeting some people shake hands. What can be said about the situation when there is an even number of handshakes and when there are an odd number of handshakes?

(See https://en.wikipedia.org/wiki/Handshaking_lemma.) - Think about graphs with n vertices. Is it possible for such graphs to have vertices of degree 0? Is it possible for such graphs to have vertices of degree $n$?
- Find all the graphs on 5 vertices all of whose vertices have the same degree.
- What graph on $n$ vertices has the most edges? What is the degree of each vertex? How many edges does it have?
- Are all graphs on 8 vertices, all of whose vertices have degree 2, isomorphic?
- Are all graphs on 4 vertices with degrees 1, 2, 2, 3 isomorphic?

From the work on Q15, students should have noticed that the sum of the degrees of a graph is always twice the number of edges. Did they manage to prove that? Did they have a better way than this?

###### Theorem

The sum of the degrees of a graph is equal to twice the number of edges.

###### Proof

Look at the edge that goes between vertices $u $and $v$. When we are considering degrees we count this edge once in the degree of $u$ and once in the degree of $v$. So this edge is counted twice in the sum of the degrees. But the same is true for any edge. Hence the result follows.

$\Box$

Questions

- What tips can you give for deciding when two graphs are isomorphic?
- What is the largest number of edges that a graph on 3, 4, 5, 6, n vertices can have? Call this number $N$. Prove that your value of $N$ is correct.
- The graph on n vertices that has $N$ edges is called the
**complete graph**on $n$ vertices and it is denoted by $K_n$. Draw $K_4$, $K_5$ and $K_6$. - Can you see any link between the graphs with $e$ edges and those with $N - e$ edges? If so, what and why?
- How many graphs are there on 5 vertices? (Use the idea of Q26 to be more efficient.)

In the light of the answers to Q11, and to the ideas that have come up in Q26 and Q27, we now want to define the complement of a graph G. The graph $\tilde{G}$ is the **complement** of $G$ if when $uv$ is an edge of $G$ it isn't an edge of $\tilde{G}$ and vice versa. This is the systematic method that we used in the answer to Q11. Next to a graph in the first column there, in the second column we have listed the complement of that graph. The same thing holds in the third and fourth columns. The graph on its own at the bottom between the third and fourth columns is a special case. It's its own complement. So it's said to be **self-complementary**.

We have talked already about graphs all of whose vertices have the same degree. In this context another useful word is 'regular'. We say that a graph, with or without loops or multiple edges, is regular if every vertex has the same degree.

Questions

- Find the complements of all the graphs on 3 vertices.
- What is the relationship between $\tilde{\tilde{G}}$ and $G$?
- Show that for a given $G$ there is only one $\tilde{G}$.
- What are the degree of the vertices in the complement of $P$? How many edges does it have?
- Find all of the regular graphs on 8 vertices that are regular of degree 5.
- Prove or disprove that the complement of a regular graph is regular. If it is true, what can be said about the degree of the complement? If it is false, show that it is false for an infinite number of regular graphs.
- Find all of the graphs on 5 vertices by using the complement idea.
- What graphs on 5 vertices are self-complementary?

The graph in Figure 7 is a regular graph of degree 3. This is the famous ** Petersen graph**. See https://en.wikipedia.org/wiki/Petersen_graph

We'll call this graph $P$. This graph has an important place in graph theory as it turns out to be a counterexample for a lot of conjectures. It is so interesting to graph theorists that a book has been written about it^{2}. Even that book doesn't contain everything that is important about the graph.

Figure 7: The Petersen graph $P$

We'll get back to $P$ later.

Questions

- What regular graphs are there on 1, 2, 3 and 4 vertices?
- Find all of the regular graphs of degree 0 on $n$ vertices. Find all of the regular graphs of degree 1 on $n$ vertices.
- Find all of the regular graphs of degree 2 on 8 vertices. Find all of the regular graphs of degree 3 on 9 vertices. Justify your answer.
- What can be said about the regular graphs of odd degree on $2n + 1$ vertices? Why? Generalise this as far as possible (i.e. not just for graphs on an odd number of vertices). Prove this result as a Corollary
^{3}of Theorem 1. - An amorous ant can only travel on edges of a graph. He and his girlfriend sit on vertices of a graph. On which of the graphs on 3, 4 and 5 graphs, can the ant be sure to be able to meet with his inamorata
^{4}?

^{2}D. Holton and J Sheehan, 1993, Petersen Graph Theory, Cambridge: Cambridge University Press

^{3}A corollary of a theorem is a result that follows easily from the theorem.

^{4}girlfriend