1. (15%) Consider the following graph. It has 20 vertices each with degree 3. Answer each of the five following questions and give a brief proof of your answer for each question. Is it a planar graph?

5. (20%) In the following, you should use uppercase letters to denote matrices and lowercase letters with subscripts to denote their entries. For example, if $M$ is a matrix, then $m_{ij}$ denotes its $(i,j)$-entry. Use lowercase letters with an arrow to denote column vectors of a matrix. For example, $\vec{m}_i$ denotes the $i$-th column vector of the matrix $M$. In your proofs, use the following definitions as needed. Definition (Equality of matrices): Matrices $A$ and $B$ are equal if they have the same size and have equal corresponding entries $a_{ij} = b_{ij}$ for all $(i,j)$. Definition (Matrix transpose): The transpose of an $m \times n$ matrix $A$ is the $n \times m$ matrix denoted by $A^T$ whose $(i,j)$-entry is the $(j,i)$-entry of $A$. Definition (Linear combination): A linear combination of vectors $\vec{u}_1, \vec{u}_2, ..., \vec{u}_k$ is a vector of the form $c_1\vec{u}_1 + c_2\vec{u}_2 + \cdots + c_k\vec{u}_k$, where $c_1, c_2, ..., c_k$ are scalars. Definition (Standard vectors): $$\vec{e}_1 = \begin{bmatrix} 1 \\ 0 \\ \vdots \\ 0 \end{bmatrix}, \vec{e}_2 = \begin{bmatrix} 0 \\ 1 \\ \vdots \\ 0 \end{bmatrix}, ..., \vec{e}_n = \begin{bmatrix} 0 \\ 0 \\ \vdots \\ 1 \end{bmatrix}$$ Now let $A$ denote a $m \times n$ matrix. Prove that $(A^T)^T = A$ and $A\vec{e}_i = \vec{a}_i$ for $i = 1, ..., n$.

1. (15%)

Consider the following graph. It has 20 vertices each with degree 3. Answer each of the five following questions and give a brief proof of your answer for each question.

Is it a planar graph?

相關申論題

相關試卷