Discrete Mathematics Homework #11

Author： Bi_Gu
发布时间：June 3, 2022
204 views
No comments
7624 words
Categories：课堂笔记离散作业离散数学

<button class="btn m-b-xs btn-light btn-roundedbtn-addon" onclick='window.open("https://cdn.dabigu.xyz/96543725_p0.png","_blank")'><i class="fa fa-camera"></i>$\quad$ **自転車 by eunyoo** </button>

# Discrete Mathematics

## Homework #11

### 1.

The graph is drawn as follows:

### 2.

Let the friendship map of that $20$ children be an undirected graph $G=(V,E)$,

with each child represented by a vertex, say, $V=\{v_1,v_2,\cdots,v_{20}\}$; and each edge of the graph shows that the corresponding pair of children are friends, say, $\{v_i,v_j\}\in E$ shows that the $i$th and $j$th children are friends.

Since $7$ of them have exactly $3$ friends, we have $\deg(v_1)=\deg(v_2)=\cdots=\deg(v_7)=3$; Similarly we have

$\deg(v_8)=\deg(v_9)=\cdots=\deg(v_{16})=4$ and $\deg(v_{17})=\deg(v_{18})=\deg(v_{19})=\deg(v_{20})=5$.

Thus we have

$$
\sum_{v\in V}\deg(v)=7\times3+9\times4+4\times5=77,
$$

which is an odd number; However from **Handshaking Theorem** we know that any $\displaystyle\sum_{v\in V}\deg(v)$ should be even since that $\displaystyle\sum_{v\in V}\deg(v)=2\left|E\right|$.

That leads to a contradiction, hence such given situation is **impossible**.

### 3.

$\textbf{(a)}$

$$
\begin{gather}
M(G_1)=\quad\begin{array}{}&
\begin{array}{}a&b&c&d\end{array}\\
\begin{array}{}a\\b\\c\\d\end{array}&
\begin{bmatrix}{}
0&1&1&0\\1&0&1&1\\1&1&0&0\\0&1&0&0
\end{bmatrix}
\end{array};\quad
M(G_2)=\quad\begin{array}{}&
\begin{array}{}a&b\end{array}\\
\begin{array}{}a\\b\end{array}&
\begin{bmatrix}{}
1&0\\0&1
\end{bmatrix}
\end{array};\\
M(G_3)=\quad\begin{array}{}&
\begin{array}{}a&b&c&d&e\end{array}\\
\begin{array}{}a\\b\\c\\d\\e\end{array}&
\begin{bmatrix}{}
0&1&0&0&0\\0&0&1&0&0\\0&0&0&0&0\\0&0&1&0&1\\1&0&0&0&0
\end{bmatrix}
\end{array};\quad
M(G_4)=\quad\begin{array}{}&
\begin{array}{}a&b&c&d\end{array}\\
\begin{array}{}a\\b\\c\\d\end{array}&
\begin{bmatrix}{}
0&1&1&0\\0&0&1&0\\0&0&0&0\\1&0&1&0
\end{bmatrix}
\end{array}.
\end{gather}
$$

$\textbf{(b)}$

$$
\begin{gather}
M(K_5)=\quad\begin{array}{}&
\begin{array}{}a&b&c&d&e\end{array}\\
\begin{array}{}a\\b\\c\\d\\e\end{array}&
\begin{bmatrix}{}
0&1&1&1&1\\1&0&1&1&1\\1&1&0&1&1\\1&1&1&0&1\\1&1&1&1&0
\end{bmatrix}
\end{array};\\
M(C_6)=\quad\begin{array}{}&
\begin{array}{}a&b&c&d&e&f\end{array}\\
\begin{array}{}a\\b\\c\\d\\e\\f\end{array}&
\begin{bmatrix}{}
0&1&0&0&0&1\\1&0&1&0&0&0\\0&1&0&1&0&0\\0&0&1&0&1&0\\0&0&0&1&0&1\\1&0&0&0&1&0
\end{bmatrix}
\end{array};\\
M(K_{2,3})=\quad\begin{array}{}&
\begin{array}{}a&b&c&d&e\end{array}\\
\begin{array}{}a\\b\\c\\d\\e\end{array}&
\begin{bmatrix}{}
0&0&1&1&1\\0&0&1&1&1\\1&1&0&0&0\\1&1&0&0&0\\1&1&0&0&0
\end{bmatrix}
\end{array}.
\end{gather}

### 4.

$\textbf{(a)}$

For $M_1$ and $M_2$, it is possible to draw the undirected graphs whose matrices are the adjacency matrices as follows:

For $M_3$ it is impossible to draw either the undirected or the directed graph since it is not a $n\times n$ matrix.

For $M_4$ it is impossible to draw the undirected graph since the matrix is not symmetric.

$\textbf{(b)}$

### 5.

$\textbf{(1)}$ $H_1$ and $H_2$ are **isomorphic** since there exists a bijection $\sigma:H_1\rightarrow H_2$ as shown below:

$$
\sigma:\quad\begin{array}{c|cccccc}
H_1&a&b&c&d&e&f\\\hline H_2&u&w&y&x&z&v
\end{array}
$$

$\textbf{(2)}$ Since that $H_1$ has $6$ vertices while $H_3$ has $5$ vertices, the number of vertices are not equal.

Which means that it's impossible to find any bijection $\sigma: H_1\rightarrow H_3$.

So that $H_1$ and $H_3$ are **nonisomorphic**.

$\textbf{(3)}$ In $H_4$ we have and only have $\deg(f)=5$; However in $H_5$ we have $\deg(w)=\deg(y)=5$.

Thus it's impossible to find any bijection $\sigma:H_4\rightarrow H_5$ since we cannot find the corresponding vertex in  $H_4$ for both $w,y$ in $H_5$ at the same time.

So that $H_4$ and $H_5$ are **nonisormorphic**.

### 6.

According to the **Theorem**, a simple graph is bipartite if and only if it is possible to assign one of two different colors to each vertex such that no two adjacent vertices have the same color. Suppose those two colors to be $\textcolor{red}{\text{red}}$ and $\textcolor{blue}{\text{blue}}$.

$\textbf{(1)}$

When $n=1$, such partition does not exist since there's only one vertex.

When $n=2$, such partition exists as follows:

$$
V_1=\{v_1\},V_2=\{v_2\}.
$$

When $n\geq 3$, suppose that we assign $\textcolor{red}{\text{red}}$ to $v_1$.

Since it is an complete graph, $v_1$ is adjacent to all of the remaining vertices, $v_2,v_3,\cdots,v_n$.

So that in order to make $K_n$ bipartite, we have to assign $\textcolor{blue}{\text{blue}}$ to $v_2,v_3,\cdots,v_n$.

However, now both $v_2$ and $v_3$ are $\textcolor{blue}{\text{blue}}$, but they are adjacent as well, which leads to the contradiction.

So that such partition does not exist when $n\geq 3$.

In conclusion, $K_n$ is bipartite when and only when $n=2$.

$\textbf{(2)}$

For $C_n$, we have $n\geq 3$ by definition.

Suppose that we assign $\textcolor{red}{\text{red}}$ to $v_1$. To make $C_n$ bipartite, since $v_1$ and $v_2$ are adjacent, we have to assign $\textcolor{blue}{\text{blue}}$ to $v_2$. Similarly, we have to assign $\textcolor{red}{\text{red}}$ to $v_3$, $\textcolor{blue}{\text{blue}}$ to $v_4$, and so on.

Now consider $v_n$. According to the color-assigning method above, we have $v_n$ to be $\textcolor{red}{\text{red}}$ when $n$ is odd, and $\textcolor{blue}{\text{blue}}$ when $n$ is even. Since it is adjacent to $v_1$, it has to be $\textcolor{blue}{\text{blue}}$ to form a bipartite graph.

So that such partition exists and only exists when $n$ is even:

$$
V_1=\{v_1,v_3,\cdots,v_{n-1}\},V_2=\{v_2,v_4,\cdots,v_n\}.
$$

In conclusion, $C_n$ is bipartite when and only when $n=2k,k\in\mathbb{N}^*$.

$\textbf{(3)}$

For $W_n$, we have $n\geq 3$ by definition.

For $W_n$, suppose that we assign $\textcolor{red}{\text{red}}$ to the vertex in the center, say $v_1$. Since it is adjacent to all the other vertices, the remaining vertices $v_2,v_3,\cdots,v_n$ have to be all $\textcolor{blue}{\text{blue}}$ in order to form a bipartite graph.

However, similar to the case in $K_n$, now that adjacent vertices $v_2,v_3$ have the same color assigned, which means that such partition does not exist.

In conclusion, $W_n$ is not bipartite under any circumstances.

$\textbf{(4)}$

According to the definition of $Q_n$, we have $V=\{0,1\}^n$. Suppose $v_i=\overline{a_{i1}a_{i2}\cdots a_{in}}$.

For every $Q_n$, such partition exists as follows:

$$
V_1=\bigg\{v_i\bigg|\sum_{k=1}^na_{ik}\in 2k,k\in\mathbb{N}\bigg\},V_2=\bigg\{v_i\bigg|\sum_{k=1}^na_{ik}\in 2k+1,k\in\mathbb{N}\bigg\}.
$$

In conclusion, $Q_n$ is bipartite for every $n\in\mathbb{N}^*$.

### 7.

$\textbf{(a)}$

$$
M=\{au,bx,cy\}
$$

is a matching for $G$ such that $\left|M\right|=3$.

$\textbf{(b)}$

$G$ is bipartite since that such partition exists as follows:

$$
V_1=\{a,b,c,d,e\},V_2=\{t,u,v,w,x,y,z\}.
$$

$(1)$ Since the number of vertices in $V_2$ is larger than the number of vertices in $V_1$, there must be some vertex in $V_2$ not matched with any vertex in $V_1$. Thus there does not exist a complete matching from $V_2$ to $V_1$.

$(2)$ Consider the vertices $a,b,e$ in $V_1$. We find that all of them are only adjacent to $u,x$ in $V_2$. Therefore there must be some vertex among the three in $V_1$ that are not matched with neither of the two in $V_2$. Thus there does not exist a complete matching from $V_1$ to $V_2$.

Last modification：June 3, 2022

Support if you like my work! qwq

版权声明：若文中无特殊说明，则本文为原创文章，版权归 Bi_Gu 所有。

本文链接：https://dabigu.xyz/index.php/archives/427/

所有原创文章采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可。
您可以自由的转载和修改，但请务必注明文章来源并且不可用于商业目的。

猜你想看 Discrete Mathematics Homework #13 Maths Analysis II - Homework #27 20220602 Maths Analysis II - Homework #26 20220531

随机文章 Linear Algebra Notes - Section 1.5 20220423 天气之子 Maths Analysis II - Homework #8 20220310

Discrete Mathematics Homework #11

Bi_Gu • 2022 年 06 月 03 日

# Discrete Mathematics

## Homework #11

### 1.

The graph is drawn as follows:

### 2.

Let the friendship map of that $20$ children be an undirected graph $G=(V,E)$,

Since $7$ of them have exactly $3$ friends, we have $\deg(v_1)=\deg(v_2)=\cdots=\deg(v_7)=3$; Similarly we have

$\deg(v_8)=\deg(v_9)=\cdots=\deg(v_{16})=4$ and $\deg(v_{17})=\deg(v_{18})=\deg(v_{19})=\deg(v_{20})=5$.

Thus we have

$$
\sum_{v\in V}\deg(v)=7\times3+9\times4+4\times5=77,
$$

which is an odd number; However from **Handshaking Theorem** we know that any $\displaystyle\sum_{v\in V}\deg(v)$ should be even since that $\displaystyle\sum_{v\in V}\deg(v)=2\left|E\right|$.

That leads to a contradiction, hence such given situation is **impossible**.

### 3.

$\textbf{(a)}$

$\textbf{(b)}$

### 4.

$\textbf{(a)}$

For $M_1$ and $M_2$, it is possible to draw the undirected graphs whose matrices are the adjacency matrices as follows:

For $M_3$ it is impossible to draw either the undirected or the directed graph since it is not a $n\times n$ matrix.

For $M_4$ it is impossible to draw the undirected graph since the matrix is not symmetric.

$\textbf{(b)}$

### 5.

$\textbf{(1)}$ $H_1$ and $H_2$ are **isomorphic** since there exists a bijection $\sigma:H_1\rightarrow H_2$ as shown below:

$$
\sigma:\quad\begin{array}{c|cccccc}
H_1&a&b&c&d&e&f\\\hline H_2&u&w&y&x&z&v
\end{array}
$$

$\textbf{(2)}$ Since that $H_1$ has $6$ vertices while $H_3$ has $5$ vertices, the number of vertices are not equal.

Which means that it's impossible to find any bijection $\sigma: H_1\rightarrow H_3$.

So that $H_1$ and $H_3$ are **nonisomorphic**.

$\textbf{(3)}$ In $H_4$ we have and only have $\deg(f)=5$; However in $H_5$ we have $\deg(w)=\deg(y)=5$.

Thus it's impossible to find any bijection $\sigma:H_4\rightarrow H_5$ since we cannot find the corresponding vertex in  $H_4$ for both $w,y$ in $H_5$ at the same time.

So that $H_4$ and $H_5$ are **nonisormorphic**.

### 6.

$\textbf{(1)}$

When $n=1$, such partition does not exist since there's only one vertex.

When $n=2$, such partition exists as follows:

$$
V_1=\{v_1\},V_2=\{v_2\}.
$$

When $n\geq 3$, suppose that we assign $\textcolor{red}{\text{red}}$ to $v_1$.

Since it is an complete graph, $v_1$ is adjacent to all of the remaining vertices, $v_2,v_3,\cdots,v_n$.

So that in order to make $K_n$ bipartite, we have to assign $\textcolor{blue}{\text{blue}}$ to $v_2,v_3,\cdots,v_n$.

However, now both $v_2$ and $v_3$ are $\textcolor{blue}{\text{blue}}$, but they are adjacent as well, which leads to the contradiction.

So that such partition does not exist when $n\geq 3$.

In conclusion, $K_n$ is bipartite when and only when $n=2$.

$\textbf{(2)}$

For $C_n$, we have $n\geq 3$ by definition.

So that such partition exists and only exists when $n$ is even:

$$
V_1=\{v_1,v_3,\cdots,v_{n-1}\},V_2=\{v_2,v_4,\cdots,v_n\}.
$$

In conclusion, $C_n$ is bipartite when and only when $n=2k,k\in\mathbb{N}^*$.

$\textbf{(3)}$

For $W_n$, we have $n\geq 3$ by definition.

However, similar to the case in $K_n$, now that adjacent vertices $v_2,v_3$ have the same color assigned, which means that such partition does not exist.

In conclusion, $W_n$ is not bipartite under any circumstances.

$\textbf{(4)}$

According to the definition of $Q_n$, we have $V=\{0,1\}^n$. Suppose $v_i=\overline{a_{i1}a_{i2}\cdots a_{in}}$.

For every $Q_n$, such partition exists as follows:

$$
V_1=\bigg\{v_i\bigg|\sum_{k=1}^na_{ik}\in 2k,k\in\mathbb{N}\bigg\},V_2=\bigg\{v_i\bigg|\sum_{k=1}^na_{ik}\in 2k+1,k\in\mathbb{N}\bigg\}.
$$

In conclusion, $Q_n$ is bipartite for every $n\in\mathbb{N}^*$.

### 7.

$\textbf{(a)}$

$$
M=\{au,bx,cy\}
$$

is a matching for $G$ such that $\left|M\right|=3$.

$\textbf{(b)}$

$G$ is bipartite since that such partition exists as follows:

$$
V_1=\{a,b,c,d,e\},V_2=\{t,u,v,w,x,y,z\}.
$$

Discrete Mathematics Homework #11

Leave a Comment Cancel reply

《Phigros》游戏记录

使用RD Client实现Windows远程桌面

基于opencv和pyautogui的腾讯会议自动入会

Discrete Mathematics Homework #13

Discrete Mathematics Homework #7

Maths Analysis II - Homework #19 20220505

Discrete Mathematics Homework #3

Math Analysis II - Homework #2 20220217

Maths Analysis II - Homework #21 20220512

Maths Analysis II - Homework #10 20220317

Discrete Mathematics Homework #11