Tutorial Exercises

1

(a) simple graph:

graph G {
	layout=circo
	Detroit--Newark
	Boston,Washington--Newark
	Miami--Newark,Detroit,Washington
}

(b) multigraph:

graph G {
	layout=circo
	
	Boston--Newark,Newark,Newark,Newark
	Newark--Boston,Boston
	Newark--Miami,Miami,Miami
	Miami--Newark,Newark
	Miami--Detroit
	Detroit--Newark,Newark
	Newark--Washington,Washington,Washington
	Washington--Newark,Newark
	Washington--Miami	
}

(c) digraph:

digraph G {
	layout=circo
	
	Boston->Newark
	Newark->Boston
	Newark->Miami
	Miami->Newark
	Miami->Detroit
	Detroit->Newark
	Newark->Washington
	Washington->Newark
	Washington->Miami	
}

title: Partially correct.
The last digraph shouldn't have multiple edges, just one directed arrow per direction.

2

(a)

1. Degrees of each vertex. $$\begin{array}{rl}\mathrm{deg}(a)& =4\\ \mathrm{deg}(b)& =1\\ \mathrm{deg}(c)& =2\\ \mathrm{deg}(d)& =3\\ \mathrm{deg}(e)& =3\\ \mathrm{deg}(f)& =2\\ \mathrm{deg}(g)& =3\\ \mathrm{deg}(h)& =2\end{array}$$
2. Identify isolated and pendant vertices. There are no isolated vertices. There is one pendant vertex: $b$
3. Connected components: a-b, a-e, a-d, a-g, d-g, d-e, d-e f-c, f-h, c-h
4. There is not a Hamiltonian cycle.

title: Correct answer.

(b)

1. Degrees of each vertex. $$\begin{array}{rl}\mathrm{deg}(1)& =2\\ \mathrm{deg}(2)& =3\\ \mathrm{deg}(3)& =3\\ \mathrm{deg}(4)& =3\\ \mathrm{deg}(5)& =3\end{array}$$
2. Identify isolated and pendant vertices. There are neither isolated nor pendant vertices.
3. Connected components: 1-4, 1-5, 2-3, 2-4, 2-5, 3-4, 3-5
4. There is a Hamiltonian cycle which takes the path $(1,4,2,3,5,1)$.

title: Correct answer.

3

Draw graph represented by:

$$\left(\begin{array}{cccc}1& 2& 0& 1\\ 2& 0& 3& 0\\ 0& 3& 1& 1\\ 1& 0& 1& 0\end{array}\right)$$

graph G {
	node[shape=point]
	a--a,b,b,d
	b--b,b,c,c,c
	c--b,b,b,c,d
	d--a,c
}

This is not a simple graph as there are multiple edges between nodes and certain nodes loop on themselves.

title: Correct answer.

4

These graphs are isomorphic, we can map one to the other using the function:

$$f(a)=1,f(b)=3,f(c)=2,f(d)=4,f(e)=5$$

title: Correct answer.
$f$ is a bijection and takes edges to edges and non-edges to non-edges.

5

Used final solutions: They are not isomorphic as they fail to satisfy the invariant “contain two disjoint subgraphs of $K_3$”.

The first graph has this property but the second doesn’t.

title: From final answers.

6

graph G {
	node[shape=point]
	subgraph cluster0 {
		a,b,c
	}
	
	subgraph cluster1 {
		d--e
		f
	}
	
	subgraph cluster2 {
		j--k--l
	}
	
	subgraph cluster3 {
		1--2
		2--3
		1--3		
	}
}

title: Partially correct.
Had all of the graphs except for the final one where the first and last node connect.

7