# Graphs study problems

### Problem 1

In the following graph, how many paths are there from a to b?
Justify your answer.

solution

### Problem 2

Here is a graph G:

How many isomorphisms are there from G to itself.

hints

solution

### Problem 3

Are these two graphs isomorphic? Justify your answer.

hints

solution

### Problem 4

Let V be a particular set of vertices of cardinality n. How many
different (simple, undirected) graphs are there with these n vertices?
Here we will assume that we are naming the edges of the graph using a
pair of vertices (so you cannot get new graphs by simply renaming edges).
Briefly justify your answer.

solution

### Problem 5

Let G be a graph with a set of nodes V and a set of edges E.
Let R be the relation on V such that uRv if and only if
there is a path from
u to v. Prove that R is an equivalence relation.

hints

solution