Discrete Mathematics Homework #12

Author： Bi_Gu
发布时间：June 7, 2022
481 views
No comments
6602 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$ **King Kong vs. Godzilla by 大猫** </button>

# Discrete Mathematics

## Homework #12

### 1.

$\textbf{(1)}$

We have

$$
κ(G_1)=1,\lambda(G_1)=3,\delta(G_1)=3.
$$

$\textbf{(2)}$

We have

$$
κ(G_2)=2,\lambda(G_1)=2,\delta(G_1)=3.
$$

$\textbf{(3)}$

We have

$$
κ(G_3)=4,\lambda(G_3)=4,\delta(G_3)=4.
$$

From which we confirm that

$$
κ(G_i)\leq\lambda(G_i)\leq\delta(G_i),i=1,2,3
$$

is true.

### 2.

The graph $G$ is **not** connected as follows:

From which we have its connected components:

$$
V_1:\{A,B,F,I\},V_2:\{D,H,K\},V_3:\{C,E,G,J\}.
$$

### 3.

Now that $G$ contains no vertices of odd degrees, which means that $\mathrm{deg}(v_{i})=2k_i,k_i\in\mathbb{N}^*$, $i=1,2,\cdots,n$.

Suppose that there exists some bridge $e=\{v_k,v_{k+1}\}\in E$. Suppose that removing $e$ gives a non-connected graph, consisting of two connected subgraphs $G_1$ and $G_2$, where

$$
V_1=\{v_1,v_2,\cdots,v_m\},V_2=\{v_{m+1},v_{m+2},\cdots,v_n\}.
$$

(Such condition must hold otherwise $G$ would not be a connected graph before removing $e$)

Now that we have

$$
\sum_{v\in V_1}\mathrm{deg}(v)=2k_1+2k_2+\cdots+2k_{m-1}+2k_m-1
$$

Which is odd; However, according to **Handshaking Theorem**, since that $G_1$ is an undirected graph, $\displaystyle\sum_{v\in V_1}\mathrm{deg}(v)=2\left|E_1\right|$ must be even. Which leads to the contradiction, thus $G$ should be bridgeless.

**The proof is complete.**

### 4.

$\textbf{(a)}$ Since that $K_{m,n}$ is a complete bipartite, we have

$$
\begin{cases}
\mathrm{deg}(v_i)=n&i=1,2,\cdots,m\\
\mathrm{deg}(v_j)=m&j=m+1,m+2,\cdots,m+n.
\end{cases}
$$

According to the **Theorem**, $K_{m,n}$ has an Euler circuit if and only if $2\mid\mathrm{deg}(x)$ for every $x\in V$.

$\mathrm{i.e.}$ $2\mid m,2\mid n$.

So that the complete bipartite $K_{m,n}$ has an Euler circuit when and only when both $m$ and $n$ are even.
$\textbf{(b)}$ Since that Euler circuits are Euler paths, $K_{m,n}$ has an Euler path when both $m,n$ are even according to $\textbf{(a)}$.

Besides Euler circuits, according to the **Theorem**, $K_{m,n}$ has an Euler path if and only if $K_{m,n}$ has exactly $2$ vertices of odd degree.

Since that $K_{m,n}$ has $m$ vertices of degree $n$ and $n$ vertices of degree $m$, such condition holds when and only when

$$
\begin{cases}
m=2\\n=2k-1,k\in\mathbb{N}^*
\end{cases}
\quad\text{or}\quad
\begin{cases}
m=2k-1,k\in\mathbb{N}^*\\n=2
\end{cases}\quad
\text{or}\quad
\begin{cases}
m=1\\n=1
\end{cases}.
$$

So that the complete bipartite $K_{m,n}$ has an Euler path when and only when both $m$ and $n$ are even, or when one of them equals to $2$ and the other is odd or both of them equal to $1$.

### 5.

$\textbf{(a)}$ Able to draw the graph without lifting the pen $\Leftrightarrow$ The graph has an Euler path.

For the first picture, we are able to draw it like this:

For the second and third picture:

The former contains $4$ vertices with odd degree, while the latter contains $8$ vertices with odd degree. (All of them marked in $\textcolor{blue}{\text{blue}}$ in the graph above.)

Thus neither of them has any Euler path, which means they can't be drawn without lifting the pen.

$\textbf{(b)}$

The first and second graph admit some Hamilton circuit, as drawn below:

For the third graph:

Since that $\mathrm{deg}(v_2)=\mathrm{deg}(v_3)=\mathrm{deg}(v_4)=2$, if there exists some Hamilton circuit, it must traverse the following edges:

$$
(v_1,v_2),(v_1,v_3),(v_1,v_4),(v_2,v_5),(v_3,v_5),(v_4,v_5),
$$

which happens to be every edge of the graph, so it actually forms an Euler circuit.

Unfortunately, we have $\mathrm{deg}(v_1)=\mathrm{deg}(v_5)=3$, which means that there exists no Euler circuit.

Thus the graph admits no Hamilton circult.

$\textbf{(c)}$

$(1)$ $G_1$ admits an Euler circuit, thus an Euler path:

$$
A\rightarrow I\rightarrow H\rightarrow F\rightarrow E\rightarrow D\rightarrow C\rightarrow B\rightarrow I\rightarrow J\rightarrow D\rightarrow F\rightarrow J\rightarrow B\rightarrow A.
$$

$(2)$ Since that $G_2$ contains $8$ vertices with odd degree (marked in $\textcolor{blue}{\text{blue}}$ above), it admits neither Euler circuit nor Euler path.

$(3)$ $G_3$ admits an Euler path:

$$
B\rightarrow A\rightarrow C\rightarrow B\rightarrow D\rightarrow C\rightarrow E\rightarrow D\rightarrow F\rightarrow E.
$$

However since it contains $2$ vertices with odd degree (marked in $\textcolor{blue}{\text{blue}}$ above), it admits no Euler circuit.

$(4)$ $G_4$ admits an Euler circuit, thus an Euler path, as shown below:

### 6.

$\textbf{(1)}$ Suppose that this graph is disconnected. Therefore, there exist two vertices that are not connected, say, $v_a$ and $v_b$.

Since that $\mathrm{deg}(v_i)=p$, there must be another $p$ vertices different from $v_j$ that are adjacent to $v_i$. Let them be $v_{a_1},v_{a_2},\cdots,v_{a_p}$; Similar $p$ vertices should exist for $v_b$, let them be $v_{b_1},v_{b_2},\cdots,v_{b_p}$.

If such condition holds that some $v_{a_i}=v_{b_j}$, then $v_a$ and $v_b$ are connected through this shared vertex, contradiction with the hypothesis. Therefore the graph contains at least $p+p+1+1=2p+2$ vertices, contradicting with the given condition that it's a simple graph with $2p$ vertices.

Therefore the graph is connected.

**The proof is complete.**

$\textbf{(2)}$ The result is the **same**.

Suppose that this graph is disconnected. Therefore, there exist two vertices that are not connected, say, $v_a$ and $v_b$.

Similar to $(1)$, we can have the result that the graph contains at least

$$
2\left\lceil\frac{n-1}{2}\right\rceil+2\geq2\cdot\frac{n-1}{2}+2=n+1
$$

vertices, contradicting with the given condition that it's a simple graph with $n$ vertices.

**The proof is complete.**

### 7.

A wheel $W_6$ is a simple connected graph with $7$ vertices but has neither Euler path nor Euler circult:

### 8.

Since that $M^n$ is not the zero matrix, there exists at least one path with length $n$.

For such path, it passes through vertices $n+1$ times. However there is only $n$ vertices in the graph, so according to **Pigeonhole Principal**, there must be a vertex which is passed at least twice.

Take out a part, if not the whole, of the path, and that forms a circuit contained by $G$.

**The proof is complete.**

Last modification：June 6, 2022

Support if you like my work! qwq

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

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

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

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

随机文章 Maths Analysis II - Homework #14 20220407 Maths Analysis II - Homework #18 20220503 Diary Set #3 20220228-20220306

Discrete Mathematics Homework #12

Bi_Gu • 2022 年 06 月 07 日

# Discrete Mathematics

## Homework #12

### 1.

$\textbf{(1)}$

We have

$$
κ(G_1)=1,\lambda(G_1)=3,\delta(G_1)=3.
$$

$\textbf{(2)}$

We have

$$
κ(G_2)=2,\lambda(G_1)=2,\delta(G_1)=3.
$$

$\textbf{(3)}$

We have

$$
κ(G_3)=4,\lambda(G_3)=4,\delta(G_3)=4.
$$

From which we confirm that

$$
κ(G_i)\leq\lambda(G_i)\leq\delta(G_i),i=1,2,3
$$

is true.

### 2.

The graph $G$ is **not** connected as follows:

From which we have its connected components:

$$
V_1:\{A,B,F,I\},V_2:\{D,H,K\},V_3:\{C,E,G,J\}.
$$

### 3.

Now that $G$ contains no vertices of odd degrees, which means that $\mathrm{deg}(v_{i})=2k_i,k_i\in\mathbb{N}^*$, $i=1,2,\cdots,n$.

Suppose that there exists some bridge $e=\{v_k,v_{k+1}\}\in E$. Suppose that removing $e$ gives a non-connected graph, consisting of two connected subgraphs $G_1$ and $G_2$, where

$$
V_1=\{v_1,v_2,\cdots,v_m\},V_2=\{v_{m+1},v_{m+2},\cdots,v_n\}.
$$

(Such condition must hold otherwise $G$ would not be a connected graph before removing $e$)

Now that we have

$$
\sum_{v\in V_1}\mathrm{deg}(v)=2k_1+2k_2+\cdots+2k_{m-1}+2k_m-1
$$

**The proof is complete.**

### 4.

$\textbf{(a)}$ Since that $K_{m,n}$ is a complete bipartite, we have

$$
\begin{cases}
\mathrm{deg}(v_i)=n&i=1,2,\cdots,m\\
\mathrm{deg}(v_j)=m&j=m+1,m+2,\cdots,m+n.
\end{cases}
$$

According to the **Theorem**, $K_{m,n}$ has an Euler circuit if and only if $2\mid\mathrm{deg}(x)$ for every $x\in V$.

$\mathrm{i.e.}$ $2\mid m,2\mid n$.

Besides Euler circuits, according to the **Theorem**, $K_{m,n}$ has an Euler path if and only if $K_{m,n}$ has exactly $2$ vertices of odd degree.

Since that $K_{m,n}$ has $m$ vertices of degree $n$ and $n$ vertices of degree $m$, such condition holds when and only when

$$
\begin{cases}
m=2\\n=2k-1,k\in\mathbb{N}^*
\end{cases}
\quad\text{or}\quad
\begin{cases}
m=2k-1,k\in\mathbb{N}^*\\n=2
\end{cases}\quad
\text{or}\quad
\begin{cases}
m=1\\n=1
\end{cases}.
$$

So that the complete bipartite $K_{m,n}$ has an Euler path when and only when both $m$ and $n$ are even, or when one of them equals to $2$ and the other is odd or both of them equal to $1$.

### 5.

$\textbf{(a)}$ Able to draw the graph without lifting the pen $\Leftrightarrow$ The graph has an Euler path.

For the first picture, we are able to draw it like this:

For the second and third picture:

The former contains $4$ vertices with odd degree, while the latter contains $8$ vertices with odd degree. (All of them marked in $\textcolor{blue}{\text{blue}}$ in the graph above.)

Thus neither of them has any Euler path, which means they can't be drawn without lifting the pen.

$\textbf{(b)}$

The first and second graph admit some Hamilton circuit, as drawn below:

For the third graph:

Since that $\mathrm{deg}(v_2)=\mathrm{deg}(v_3)=\mathrm{deg}(v_4)=2$, if there exists some Hamilton circuit, it must traverse the following edges:

$$
(v_1,v_2),(v_1,v_3),(v_1,v_4),(v_2,v_5),(v_3,v_5),(v_4,v_5),
$$

which happens to be every edge of the graph, so it actually forms an Euler circuit.

Unfortunately, we have $\mathrm{deg}(v_1)=\mathrm{deg}(v_5)=3$, which means that there exists no Euler circuit.

Thus the graph admits no Hamilton circult.

$\textbf{(c)}$

$(1)$ $G_1$ admits an Euler circuit, thus an Euler path:

$$
A\rightarrow I\rightarrow H\rightarrow F\rightarrow E\rightarrow D\rightarrow C\rightarrow B\rightarrow I\rightarrow J\rightarrow D\rightarrow F\rightarrow J\rightarrow B\rightarrow A.
$$

$(2)$ Since that $G_2$ contains $8$ vertices with odd degree (marked in $\textcolor{blue}{\text{blue}}$ above), it admits neither Euler circuit nor Euler path.

$(3)$ $G_3$ admits an Euler path:

$$
B\rightarrow A\rightarrow C\rightarrow B\rightarrow D\rightarrow C\rightarrow E\rightarrow D\rightarrow F\rightarrow E.
$$

However since it contains $2$ vertices with odd degree (marked in $\textcolor{blue}{\text{blue}}$ above), it admits no Euler circuit.

$(4)$ $G_4$ admits an Euler circuit, thus an Euler path, as shown below:

### 6.

$\textbf{(1)}$ Suppose that this graph is disconnected. Therefore, there exist two vertices that are not connected, say, $v_a$ and $v_b$.

Therefore the graph is connected.

**The proof is complete.**

$\textbf{(2)}$ The result is the **same**.

Suppose that this graph is disconnected. Therefore, there exist two vertices that are not connected, say, $v_a$ and $v_b$.

Similar to $(1)$, we can have the result that the graph contains at least

$$
2\left\lceil\frac{n-1}{2}\right\rceil+2\geq2\cdot\frac{n-1}{2}+2=n+1
$$

vertices, contradicting with the given condition that it's a simple graph with $n$ vertices.

**The proof is complete.**

### 7.

A wheel $W_6$ is a simple connected graph with $7$ vertices but has neither Euler path nor Euler circult:

### 8.

Since that $M^n$ is not the zero matrix, there exists at least one path with length $n$.

Take out a part, if not the whole, of the path, and that forms a circuit contained by $G$.

**The proof is complete.**

Discrete Mathematics Homework #12

Leave a Comment Cancel reply

《Phigros》游戏记录

使用RD Client实现Windows远程桌面

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

Introduction to Machine Learning Homework #2

Probability and Mathematic Stastics Homework #1

CS101 Lecture#1 Introduction

20220514 祝自己生日快乐

Maths Analysis II - Homework #25 20220526

Maths Analysis II - Homework #13 20220329

Linear Algebra Notes - Section 1.4

Discrete Mathematics Homework #12