2

(a)

$$ D=\begin{bmatrix} 4 & 0 & 0 & 0 & 0 & 0\\ 0 & 4 & 0 & 0 & 0 & 0\\ 0 & 0 & 2 & 0 & 0 & 0\\ 0 & 0 & 0 & 2 & 0 & 0\\ 0 & 0 & 0 & 0 & 2 & 0\\ 0 & 0 & 0 & 0 & 0 & 2\\\end{bmatrix}, A=\begin{bmatrix} 0 & 1 & 1 & 1 & 1 & 1\\ 1 & 0 & 1 & 1 & 1 & 1\\ 1 & 1 & 0 & 0 & 0 & 0\\ 1 & 1 & 0 & 0 & 0 & 0\\ 1 & 1 & 0 & 0 & 0 & 0\\ 1 & 1 & 0 & 0 & 0 & 0\\\end{bmatrix} $$

$$ Q=D-A=\begin{bmatrix} 4 & -1 & -1 & -1 & -1 & -1\\ -1 & 4 & -1 & -1 & -1 & -1\\ -1 & -1 & 2 & 0 & 0 & 0\\ -1 & -1 & 0 & 2 & 0 & 0\\ -1 & -1 & 0 & 0 & 2 & 0\\ -1 & -1 & 0 & 0 & 0 & 2\\\end{bmatrix} $$

$$ (-1)^{1+1}\det Q_{1,1}=\det \begin{bmatrix} 4 & -1 & -1 & -1 & -1\\ -1 & 2 & 0 & 0 & 0\\ -1 & 0 & 2 & 0 & 0\\ -1 & 0 & 0 & 2 & 0\\ -1 & 0 & 0 & 0 & 2\\\end{bmatrix}=4\det \begin{bmatrix} 2 & 0 & 0 & 0\\ 0 & 2 & 0 & 0\\ 0 & 0 & 2 & 0\\ 0 & 0 & 0 & 2\\\end{bmatrix} -(-1)\det \begin{bmatrix} -1 & 0 & 0 & 0\\ -1 & 2 & 0 & 0\\ -1 & 0 & 2 & 0\\ -1 & 0 & 0 & 2\\\end{bmatrix} +(-1)\det \begin{bmatrix} -1 & 2 & 0 & 0\\ -1 & 0 & 0 & 0\\ -1 & 0 & 2 & 0\\ -1 & 0 & 0 & 2\\\end{bmatrix} -(-1)\det \begin{bmatrix} -1 & 2 & 0 & 0\\ -1 & 0 & 2 & 0\\ -1 & 0 & 0 & 0\\ -1 & 0 & 0 & 2\\\end{bmatrix} +(-1)\det \begin{bmatrix} -1 & 2 & 0 & 0\\ -1 & 0 & 2 & 0\\ -1 & 0 & 0 & 2\\ -1 & 0 & 0 & 0\\\end{bmatrix}=64-4*8=32 $$

(b)

Answer is 2.

In the below image, the 2-vertex part of $K_{2,4}$ is colored in gray.

Since we’re considering no-label graph, we are free to pin a gray vertex as root. Then the only three possible cases are $G_1, G_2, G_3$ as illustrated below. However, notice that the last two are isomorphic. The first two are not isomorphic since $\Delta(G_1)=4, \Delta(G_2)=3$. Therefore only 2 non-isomorphic cases.

3

Use the Kruskal’s algorithm. Denote the answer of $Q_k$ as $f(k)$. The edges with smallest weight are those having weight $2^1$. All $2^{k-1}$ of them can be added into the edge set, since they are all disjoint due to the two endpoints $(0, x_2, \dots x_k) - (1, x_2, \dots x_k)$. After adding them, the graph consists of $2^{k-1}$ connected components.

In the base case of $k=1$, $f(1)=2^1$.

Otherwise, $k > 1$. By viewing every component as point, since the first coordinate is no longer important to check connectivity in Kruskal’s algorithm, the remaining problem becomes the minimum weight of a spanning tree in $Q_{k-1}$ but with doubled weights, thus $f(k)=2^1 * 2^{k-1} + 2 * f(k-1)$.

In summary, $\frac{f(1)}{2^1}=1; \forall k>1, \frac{f(k)}{2^k}=\frac{f(k-1)}{2^{k-1}}+1$, therefore $f(k)=k2^k$.

4

(a)

k-regular bipartite graph $G=(X,Y;E)$. As shown in the proof of marriage theorm, $|X| = |Y|$.

• Case 1: $\exists S, \emptyset \ne S \subsetneq X, |N(S)| \le |S|$. In the induced subgraph G’ from $S \cup N(S)$, there are $k|S|$ edges, which means there are $k|S|$ edges in G’ incident with $N(S)$. OTAH, the total number of edges incident with $N(S)$, which is supposed to be not least than the ones in G’, is $k|N(S)|$, which is at most $k|S|$. Therefore we must have $|N(S)| =|S|$. In this case, however, G’ is isolated from the rest of the graph G, making G disconnected and contradicting to the condition of G being connected.
• Case 2: $\forall S, \emptyset \ne S \subsetneq X \to |N_G(S)| \ge |S| +1$. Then after removing two arbitrary vertices $x,y$, the resulting graph $G’’:=G-x-y$ have $\forall S', \emptyset \ne S \subset X\setminus \{x\}, |N_{G''}(S')| \ge |N_{G}(S')|-1 \ge |S'|$, according to the case condition. For $S’=\emptyset, |N_{G''}(S')| \ge |S'|$ is trivially true. By Hall’s thm, $G''$ has a matching that covers $X\setminus \{x\}$. Since $|X\setminus \{x\}| = |Y\setminus \{y\}|$, it is a perfect matching.