### 数学代写|图论作业代写Graph Theory代考|MTH607

statistics-lab™ 为您的留学生涯保驾护航 在代写图论Graph Theory方面已经树立了自己的口碑, 保证靠谱, 高质且原创的统计Statistics代写服务。我们的专家在代写图论Graph Theory代写方面经验极为丰富，各种代写图论Graph Theory相关的作业也就用不着说。

## 数学代写|图论作业代写Graph Theory代考|Ramsey properties and connectivity

According to Ramsey’s theorem, every large enough graph $G$ has a very dense or a very sparse induced subgraph of given order, a $K^r$ or $\overline{K^r}$. If we assume that $G$ is connected, we can say a little more:

Proposition 9.4.1. For every $r \in \mathbb{N}$ there is an $n \in \mathbb{N}$ such that every connected graph of order at least $n$ contains $K^r, K_{1, r}$ or $P^r$ as an induced subgraph.

Proof. Let $d+1$ be the Ramsey number of $r$, let $n:=\frac{d}{d-2}(d-1)^r$, and let $G$ be a graph of order at least $n$. If $G$ has a vertex $v$ of degree at least $d+1$ then, by Theorem 9.1.1 and the choice of $d$, either $N(v)$ induces a $K^r$ in $G$ or ${v} \cup N(v)$ induces a $K_{1, r}$. On the other hand, if $\Delta(G) \leqslant d$, then by Proposition 1.3.3 $G$ has radius $>r$, and hence contains two vertices at a distance $\geqslant r$. Any shortest path in $G$ between these two vertices contains a $P^r$.

In principle, we could now look for a similar set of ‘unavoidable’ $k$-connected subgraphs for any given connectivity $k$. To keep thse ‘unavoidable sets’ small, it helps to relax the containment relation from ‘induced subgraph’ for $k=1$ (as above) to ‘topological minor’ for $k=2$, and on to ‘minor’ for $k=3$ and $k=4$. For larger $k$, no similar results are known.

Proposition 9.4.2. For every $r \in \mathbb{N}$ there is an $n \in \mathbb{N}$ such that every 2-connected graph of order at least $n$ contains $C^r$ or $K_{2, r}$ as a topological minor.

Proof. Let $d$ be the $n$ associated with $r$ in Proposition 9.4.1, and let $G$ be a 2-connected graph with at least $\frac{d}{d-2}(d-1)^r$ vertices. By Proposition 1.3.3, either $G$ has a vertex of degree $>d$ or $\operatorname{diam} G \geqslant \operatorname{rad} G>r$.

In the latter case let $a, b \in G$ be two vertices at distance $>r$. By Menger’s theorem (3.3.6), $G$ contains two independent $a-b$ paths. These form a cycle of length $>r$.

## 数学代写|图论作业代写Graph Theory代考|Simple sufficient conditions

What kind of condition might be sufficient for the existence of a Hamilton cycle in a graph $G$ ? Purely global assumptions, like high edge density, will not be enough: we cannot do without the local property that every vertex has at least two neighbours. But neither is any large (but constant) minimum degree sufficient: it is easy to find graphs without a Hamilton cycle whose minimum degree exceeds any given constant bound.
The following classic result derives its significance from this background:

Theorem 10.1.1. (Dirac 1952)
Every graph with $n \geqslant 3$ vertices and minimum degree at least $n / 2$ has a Hamilton cycle.

Proof. Let $G=(V, E)$ be a graph with $|G|=n \geqslant 3$ and $\delta(G) \geqslant n / 2$. Then $G$ is connected: otherwise, the degree of any vertex in the smallest component $C$ of $G$ would be less than $|C| \leqslant n / 2$.

Let $P=x_0 \ldots x_k$ be a longest path in $G$. By the maximality of $P$, all the neighbours of $x_0$ and all the neighbours of $x_k$ lie on $P$. Hence at least $n / 2$ of the vertices $x_0, \ldots, x_{k-1}$ are adjacent to $x_k$, and at least $n / 2$ of these same $k<n$ vertices $x_i$ are such that $x_0 x_{i+1} \in E$. By the pigeon hole principle, there is a vertex $x_i$ that has both properties, so we have $x_0 x_{i+1} \in E$ and $x_i x_k \in E$ for some $i<k$ (Fig. 10.1.1).

We claim that the cycle $C:=x_0 x_{i+1} P x_k x_i P x_0$ is a Hamilton cycle of $G$. Indeed, since $G$ is connected, $C$ would otherwise have a neighbour in $G-C$, which could be combined with a spanning path of $C$ into a path longer than $P$.

# 图论代考

## Matlab代写

MATLAB 是一种用于技术计算的高性能语言。它将计算、可视化和编程集成在一个易于使用的环境中，其中问题和解决方案以熟悉的数学符号表示。典型用途包括：数学和计算算法开发建模、仿真和原型制作数据分析、探索和可视化科学和工程图形应用程序开发，包括图形用户界面构建MATLAB 是一个交互式系统，其基本数据元素是一个不需要维度的数组。这使您可以解决许多技术计算问题，尤其是那些具有矩阵和向量公式的问题，而只需用 C 或 Fortran 等标量非交互式语言编写程序所需的时间的一小部分。MATLAB 名称代表矩阵实验室。MATLAB 最初的编写目的是提供对由 LINPACK 和 EISPACK 项目开发的矩阵软件的轻松访问，这两个项目共同代表了矩阵计算软件的最新技术。MATLAB 经过多年的发展，得到了许多用户的投入。在大学环境中，它是数学、工程和科学入门和高级课程的标准教学工具。在工业领域，MATLAB 是高效研究、开发和分析的首选工具。MATLAB 具有一系列称为工具箱的特定于应用程序的解决方案。对于大多数 MATLAB 用户来说非常重要，工具箱允许您学习应用专业技术。工具箱是 MATLAB 函数（M 文件）的综合集合，可扩展 MATLAB 环境以解决特定类别的问题。可用工具箱的领域包括信号处理、控制系统、神经网络、模糊逻辑、小波、仿真等。