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