Practice Work

1

1. Degree of vertices:

   $$\begin{array}{rl}\mathrm{deg}(v_1)& =2\\ \mathrm{deg}(v_2)& =5\\ \mathrm{deg}(v_3)& =1\text{ is pendant}\\ \mathrm{deg}(v_4)& =2\\ \mathrm{deg}(v_5)& =3\\ \mathrm{deg}(v_6)& =4\\ \mathrm{deg}(v_7)& =3\end{array}$$

   title: Correct answer.

2. It is not a path as there is no valid path between $v_2$ and $v_5$.

   title: Correct answer.
   A path is a sequence of vertices travelling along edges, but there is no edge between $v_2$ and $v_5$.

3. It is a simple cycle as there are no duplicate edges.

   title: Correct answer.

4. Adjacency matrix:

   $$\begin{array}{cccccccc}& v_1& v_2& v_3& v_4& v_5& v_6& v_7\\ v_1& 0& 1& 0& 0& 0& 1& 0\\ v_2& 1& 0& 1& 1& 0& 1& 1\\ v_3& 0& 1& 0& 0& 0& 0& 0\\ v_4& 0& 1& 0& 0& 1& 0& 0\\ v_5& 0& 0& 0& 1& 0& 1& 1\\ v_6& 1& 1& 0& 0& 1& 0& 1\\ v_7& 0& 1& 0& 0& 1& 1& 0\end{array}$$

   title: Correct answer.

2

graph A {
	node[shape=point]
 
	a--f,e,d
	b--c,d,e
	f--c,e
	d--c
}
 
graph B {
	node[shape=point]
 
	1--2,3,5
	2--3,6
	4--5,6
	5--6
}

Consider the invariant “containing two disjoint $K_3$ subgraphs”. The invariant holds for $G_2$ but not for $G_1$, hence the graphs are not isomorphic.

title: Wrong answer.
You can show an isomorphism by taking edges-to-edges and non-edges to non-edges using:
 
$$
	g(a) = 1, \, g(b) = 4, \, g(c) = 6, \, g(d) = 5, \, g(e) = 3, \, g(f) = 2
$$