Tutorial Exercises

1

1. $G_1$ is a tree as you can take $b$, $5$ or $f$ as a root node and can arrange everything to descend from the node.
2. $G_2$ is a tree as you can take $a$, $5$, or $f$ as a root node.
3. $G_3$ is not a tree as there is a cycle formed: $(3,b,2,a,1,c,3)$
4. $G_4$ is not a tree as there are two disjoint simple graphs.

title: Correct answers.
Could use different terminology though, say, "$G_1$ and $G_2$ are each connected and contains no simple cycles so it is a tree."

2

1. Root is $a$
2. Internal vertices are: $a,b,c,d,f,g,h,j,q,t$
3. Leaves are $e,l,m,n,g,o,p,s,i,u,r,k$
4. Children of $j$ are: $q,r$
5. Parent of $h$ is $c$
6. Sibling of $o$ is $p$
7. Ancenstors of $m$ are $f,b,a$
8. Descendants of $b$ are $e,f,l,m,n$

title: Correct answers.

3

No, say it was a full $3-ary$ tree, $a$ satisfies this by having $3$ children but $b$ only has $2$ children so it can’t be a full $3-ary$ tree.

title: Correct answer.

4

Basis Step: Take a tree with $n=1$ vertices, it is just the root so we know that it doesn’t have any edges, according to the statement, it should have $n-1=1-1=0$ edges which is correct.

Inductive Step: Assume that for $n=k$, every tree with $k$ vertices has $k-1$ edges.

Now try to prove this for $n=k+1$, lets assume we already have a graph $T$ which has $k$ vertices, now we add another vertex, make it the root and make the root of $T$ the child of this new vertex. By IH, we know that the number of edges of $T$ is $k-1$, but we also know that since we just added our new root vertex, there is now a new edge between our root and $T$‘s original root.

Hence, the number of edges is now $k-1+1$, which is $k$ or otherwise $(k+1)-1$. This is the IH with $n=k+1$.

graph G {
	node[shape=point]
	0[xlabel="new vertex / root"]
 
	0--1
	
	subgraph cluster0 {
		label="        T"
		1[xlabel="root "]
		1--2,3
		2--4,5
		3--6,7
	}
}

Hence by mathematical induction, for all positive integers $n$, every tree with $n$ vertices has $n-1$ edges.

title: Correct answer.

5

1. It is a simple graph but it is cyclic, hence not a tree.

   graph G {
   	1--3,5
    2--4,5
    3--4
   }

   title: Correct answer.

2. It is a simple graph and has no simple cycles, hence it is a tree.

   graph G {
   	1--2
    2--3,5
    3--4
   }

   title: Correct answer.

3. It is a simple graph with no cycles, hence it is a tree.

   graph G {
   	1--2
    2--3
    3--4
   }

   title: Graph is not connected hence not a tree.
      ```graphviz
      graph G {
   	1--2
   	2--3
   	3--4
   	5
      }

6

1. Full binary tree having 4 internal vertices and five leaves.

   graph G {
   	node[shape=point]
    0--l,r
    l--aa
    l--1
    1--bb
    1--2
    2--cc,dd
   }

   title: Correct answer.

2. Full binary tree of height 3 and having nine leaves. is not possible, as the maximum is eight leaves

   title: Correct answer.

   graph G {
   	node[shape=point]
    0--1,2
    1--3,4
    3--5,6
    4--7,8
    2--9,10
    9--11,12
    10--13,14
   }

3. Full binary tree of height $4$ having nine leaves.

   graph G {
   	node[shape=point]
    0--1,2
    1--3,4
    3--5,6
    4--7,8
    2--9,10
    9--11,12
    10--13,14
    14--15,16
   }

   title: Correct answer.

7

graph G {
	graph [nodesep="0.6"]
	node[shape=plain]
 
	1[label="∨"]
	2[label="∧"]
	3[label="¬"]
	4[label="q"]
	5[label="¬"]
	6[label="p"]
	7[label="↔"]
	8[label="q"]
	9[label="¬"]
	10[label="p"]
	
	1--2,3
	3--4
	2--5,7
	5--6
	7--8,9
	9--10
}

title: Correct answer.

8

graph G {
	layout=neato
	graph[nodesep="0.6"]
	node[shape=plain]
	
	15[pos="0,0!"]
	3[pos="-1,-1!"]
	627[pos="1,-1!"]
	410[pos="0, -2!"]
	512[pos="1,-3!"]
	626[pos="2,-4!"]
	
	15--3,627
	627--410
	410--512
	512--626
}

1. To locate or add $512$, $4$ comparisons are needed.
2. To locate or add $408$, $3$ comparisons are needed.

title: Correct answers.

9

1. Pre-order: $a,b,e,f,l,m,n,c,g,h,o,p,d,i,j,q,s,t,u,r,k$
2. In-order: $e,b,l,f,m,n,g,c,a,o,h,p,i,s,q,j,d,u,t,r,k$
3. Post-order: $e,l,m,n,f,b,g,o,p,i,h,c,s,u,t,q,r,j,k,d,a$

title: Partially correct.
In-order is incorrect, should be $e,b,l,f,m,n,a,g,c,o,h,p,i,d,s,q,u,t,j,r,k$