Problem $03(20$ points$)$

Let $|)$:$\}$ is a multiple of $\{$:$n\}.$ Show that for each $n1,$ the language $B_n$ is regular.

Hint: Construct the base case for $n=1$ and then construct a DFA for $n=2$ and notice what

changes. Then use what you learned to complete the proof.

Hint: If you really get stuck, and you've already produced state diagrams for the $n=1$ and $n=2$

cases, try producing a state diagram for the $n=3$ case and consider what changes when going from

$n=2$ to $n=3$

$(2)$ Minimum Spanning Trees

$(2\mathrm{.}1)$ List the sequence of edges selected by Kruskal's algorithm when it is applied to the following graph. $[4$ points$]$

$1$

$(2\mathrm{.}2)$ Show an edge that demonstrates the Cut Property: list the edge and the two relevant node sets. $[2$ points$]$

$(2\mathrm{.}3)$ Show an edge that demonstrates the Cycle Property: list the edge and the relevant cycle. $[2$ points$]$