如果你也在 怎样代写图论Graph Theory 这个学科遇到相关的难题，请随时右上角联系我们的24/7代写客服。图论Graph Theory有趣的部分原因在于，图可以用来对某些问题中的情况进行建模。这些问题可以在图表的帮助下进行研究(并可能得到解决)。因此，图形模型在本书中经常出现。然而，图论是数学的一个领域，因此涉及数学思想的研究-概念和它们之间的联系。我们选择包含的主题和结果是因为我们认为它们有趣、重要和/或代表主题。

图论Graph Theory通过熟悉许多过去和现在对图论的发展负责的人，可以增强对图论的欣赏。因此，我们收录了一些关于“图论人士”的有趣评论。因为我们相信这些人是图论故事的一部分，所以我们在文中讨论了他们，而不仅仅是作为脚注。我们常常没有认识到数学是一门有生命的学科。图论是人类创造的，是一门仍在不断发展的学科。

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

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

Let $H$ be a graph and $n \geqslant|H|$. How many edges will suffice to force an $H$ subgraph in any graph on $n$ vertices, no matter how these edges are arranged? Or, to rephrase the problem: which is the greatest possible number of edges that a graph on $n$ vertices can have without containing a copy of $H$ as a subgraph? What will such a graph look like? Will it be unique?

A graph $G \nsupseteq H$ on $n$ vertices with the largest possible number of edges is called extremal for $n$ and $H$; its number of edges is denoted by $\operatorname{ex}(n, H)$. Clearly, any graph $G$ that is extremal for some $n$ and $H$ will also be edge-maximal with $H \nsubseteq G$. Conversely, though, edge-maximality does not imply extremality: $G$ may well be edge-maximal with $H \nsubseteq G$ while having fewer than $\operatorname{ex}(n, H)$ edges (Fig. 7.1.1).

As a case in point, we consider our problem for $H=K^r$ (with $r>1$ ). A moment’s thought suggests some obvious candidates for extremality here: all complete $(r-1)$-partite graphs are edge-maximal without containing $K^r$. But which among these have the greatest number of edges? Clearly those whose partition sets are as equal as possible, i.e. differ in size by at most 1: if $V_1, V_2$ are two partition sets with $\left|V_1\right|-\left|V_2\right| \geqslant 2$, we may increase the number of edges in our complete $(r-1)$-partite graph by moving a vertex from $V_1$ to $V_2$.

The unique complete $(r-1)$-partite graphs on $n \geqslant r-1$ vertices whose partition sets differ in size by at most 1 are called Turán graphs; we denote them by $T^{r-1}(n)$ and their number of edges by $t_{r-1}(n)$ (Fig. 7.1.2). For $n<r-1$ we shall formally continue to use these definitions, with the proviso that – contrary to our usual terminologythe partition sets may now be empty; then, clearly, $T^{r-1}(n)=K^n$ for all $n \leqslant r-1$.

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

In the context of flows, we have to be able to speak about the ‘directions’ of an edge. Since, in a multigraph $G=(V, E)$, an edge $e=x y$ is not identified uniquely by the pair $(x, y)$ or $(y, x)$, we define directed edges as triples:
$$
\vec{E}:={(e, x, y) \mid e \in E ; x, y \in V ; e=x y} .
$$
Thus, an edge $e=x y$ with $x \neq y$ has the two directions $(e, x, y)$ and $(e, y, x)$; a loop $e=x x$ has only one direction, the triple $(e, x, x)$. For given $\vec{e}=(e, x, y) \in \vec{E}$, we set $\bar{e}:=(e, y, x)$, and for an arbitrary set $\vec{F} \subseteq \vec{E}$ of edge directions we put
$$
\bar{F}:={\bar{e} \mid \vec{e} \in \vec{F}}
$$
Note that $\vec{E}$ itself is symmetrical: $\bar{E}=\vec{E}$. For $X, Y \subseteq V$ and $\vec{F} \subseteq \vec{E}$, define
$$
\vec{F}(X, Y):={(e, x, y) \in \vec{F} \mid x \in X ; y \in Y ; x \neq y},
$$
abbreviate $\vec{F}({x}, Y)$ to $\vec{F}(x, Y)$ etc., and write
$$
\vec{F}(x):=\vec{F}(x, V)=\vec{F}({x}, \overline{{x}}) .
$$
Here, as below, $\bar{X}$ denotes the complement $V \backslash X$ of a vertex set $X \subseteq V$. Note that any loops at vertices $x \in X \cap Y$ are disregarded in the definitions of $\vec{F}(X, Y)$ and $\vec{F}(x)$.

Let $H$ be an abelian semigroup, ${ }^2$ written additively with zero 0 . Given vertex sets $X, Y \subseteq V$ and a function $f: \vec{E} \rightarrow H$, let
$$
f(X, Y):=\sum_{\vec{e} \in \vec{E}(X, Y)} f(\vec{e})
$$

图论代考

数学代写|图论作业代写Graph Theory代考|Perfect graphs

正如第5.2节所讨论的，高色数可能作为一种纯粹的全局现象出现:即使一个图有很大的周长，因此局部看起来像一棵树，它的色数可能是任意高的。由于这种“全局依赖”显然很难处理，人们可能会对不发生这种现象的图感兴趣，即只有在存在局部原因的情况下，其色数才高。
在我们明确这一点之前，让我们注意图$G$的两个定义。最大的整数$r$使得$K^r \subseteq G$是$G$的团数$\omega(G)$，最大的整数$r$使得$\overline{K^r} \subseteq G$(诱导)是$G$的独立数$\alpha(G)$。显然是$\alpha(G)=\omega(\bar{G})$和$\omega(G)=\alpha(\bar{G})$。
如果每个诱导子图$H \subseteq G$都有色数$\chi(H)=\omega(H)$，即$\omega(H)$颜色的平凡下界总是足以为$H$的顶点上色，则称为完美图。因此，虽然证明形式为$\chi(G)>k$的断言通常是困难的，即使在原则上，对于给定的图$G$，它总是可以通过简单地展示一些$K^{k+1}$子图作为具有$k$颜色的不可着色性的“证书”来完成。

乍一看，完美图类的结构似乎有些做作:虽然它在诱导子图下是封闭的(如果仅通过显式定义)，但它在取一般子图或超图时并不封闭，更不用说子图了(例子?)然而，完美性在图论中是一个重要的概念:图的几个基本类是完美的(似乎是侥幸)，这一事实可能是这一点的表面迹象。 ${ }^3$

那么，什么样的图表是完美的呢?例如，二部图。不那么平凡的是，二部图的补也是完美的，这一事实等价于König的对偶定理2.1.1(练习36)。所谓的可比性图是完美的，区间图也是如此(参见练习);这两种情况在许多应用程序中都会出现。

为了详细地研究至少一个这样的例子，我们在这里证明弦图是完美的:一个图是弦图(或三角图)，如果它的每个长度至少为4的环都有一个弦，即，如果它不包含除三角形以外的诱导环。

为了证明弦图是完美的，我们将首先描述弦图的结构。如果$G$是一个具有诱导子图$G_1, G_2$和$S$的图，例如$G=G_1 \cup G_2$和$S=G_1 \cap G_2$，我们说$G$是由$G_1$和$G_2$通过沿着$S$粘贴在一起而产生的。

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

在流动的背景下，我们必须能够谈论边缘的“方向”。由于在多图$G=(V, E)$中，边$e=x y$不是由$(x, y)$或$(y, x)$对唯一标识的，因此我们将有向边定义为三元组:
$$
\vec{E}:={(e, x, y) \mid e \in E ; x, y \in V ; e=x y} .
$$
因此，具有$x \neq y$的边$e=x y$具有$(e, x, y)$和$(e, y, x)$两个方向;一个循环$e=x x$只有一个方向，即三重$(e, x, x)$。对于给定的$\vec{e}=(e, x, y) \in \vec{E}$，我们设置$\bar{e}:=(e, y, x)$，对于任意的边方向集$\vec{F} \subseteq \vec{E}$，我们设置
$$
\bar{F}:={\bar{e} \mid \vec{e} \in \vec{F}}
$$
注意$\vec{E}$本身是对称的:$\bar{E}=\vec{E}$。对于$X, Y \subseteq V$和$\vec{F} \subseteq \vec{E}$，定义
$$
\vec{F}(X, Y):={(e, x, y) \in \vec{F} \mid x \in X ; y \in Y ; x \neq y},
$$
将$\vec{F}({x}, Y)$缩写为$\vec{F}(x, Y)$等，并写上
$$
\vec{F}(x):=\vec{F}(x, V)=\vec{F}({x}, \overline{{x}}) .
$$
下面，$\bar{X}$表示顶点集$X \subseteq V$的补$V \backslash X$。注意，在$\vec{F}(X, Y)$和$\vec{F}(x)$的定义中，顶点$x \in X \cap Y$处的任何循环都将被忽略。

设$H$是一个阿贝尔半群，${ }^2$与0相加。给定顶点集$X, Y \subseteq V$和函数$f: \vec{E} \rightarrow H$，设
$$
f(X, Y):=\sum_{\vec{e} \in \vec{E}(X, Y)} f(\vec{e})
$$

统计代写请认准statistics-lab™. statistics-lab™为您的留学生涯保驾护航。

如果你也在 怎样代写图论Graph Theory 这个学科遇到相关的难题，请随时右上角联系我们的24/7代写客服。图论Graph Theory有趣的部分原因在于，图可以用来对某些问题中的情况进行建模。这些问题可以在图表的帮助下进行研究(并可能得到解决)。因此，图形模型在本书中经常出现。然而，图论是数学的一个领域，因此涉及数学思想的研究-概念和它们之间的联系。我们选择包含的主题和结果是因为我们认为它们有趣、重要和/或代表主题。

图论Graph Theory通过熟悉许多过去和现在对图论的发展负责的人，可以增强对图论的欣赏。因此，我们收录了一些关于“图论人士”的有趣评论。因为我们相信这些人是图论故事的一部分，所以我们在文中讨论了他们，而不仅仅是作为脚注。我们常常没有认识到数学是一门有生命的学科。图论是人类创造的，是一门仍在不断发展的学科。

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

数学代写|图论作业代写Graph Theory代考|Perfect graphs

As discussed in Section 5.2, a high chromatic number may occur as a purely global phenomenon: even when a graph has large girth, and thus locally looks like a tree, its chromatic number may be arbitrarily high. Since such ‘global dependence’ is obviously difficult to deal with, one may become interested in graphs where this phenomenon does not occur, i.e. whose chromatic number is high only when there is a local reason for it.
Before we make this precise, let us note two definitions for a graph $G$. The greatest integer $r$ such that $K^r \subseteq G$ is the clique number $\omega(G)$ of $G$, and the greatest integer $r$ such that $\overline{K^r} \subseteq G$ (induced) is the independence number $\alpha(G)$ of $G$. Clearly, $\alpha(G)=\omega(\bar{G})$ and $\omega(G)=\alpha(\bar{G})$.
A graph is called perfect if every induced subgraph $H \subseteq G$ has chromatic number $\chi(H)=\omega(H)$, i.e. if the trivial lower bound of $\omega(H)$ colours always suffices to colour the vertices of $H$. Thus, while proving an assertion of the form $\chi(G)>k$ may in general be difficult, even in principle, for a given graph $G$, it can always be done for a perfect graph simply by exhibiting some $K^{k+1}$ subgraph as a ‘certificate’ for non-colourability with $k$ colours.

At first glance, the structure of the class of perfect graphs appears somewhat contrived: although it is closed under induced subgraphs (if only by explicit definition), it is not closed under taking general subgraphs or supergraphs, let alone minors (examples?). However, perfection is an important notion in graph theory: the fact that several fundamental classes of graphs are perfect (as if by fluke) may serve as a superficial indication of this. ${ }^3$

What graphs, then, are perfect? Bipartite graphs are, for instance. Less trivially, the complements of bipartite graphs are perfect, tooa fact equivalent to König’s duality theorem 2.1.1 (Exercise 36). The so-called comparability graphs are perfect, and so are the interval graphs (see the exercises); both these turn up in numerous applications.

In order to study at least one such example in some detail, we prove here that the chordal graphs are perfect: a graph is chordal (or triangulated) if each of its cycles of length at least 4 has a chord, i.e. if it contains no induced cycles other than triangles.

To show that chordal graphs are perfect, we shall first characterize their structure. If $G$ is a graph with induced subgraphs $G_1, G_2$ and $S$, such that $G=G_1 \cup G_2$ and $S=G_1 \cap G_2$, we say that $G$ arises from $G_1$ and $G_2$ by pasting these graphs together along $S$.

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

In the context of flows, we have to be able to speak about the ‘directions’ of an edge. Since, in a multigraph $G=(V, E)$, an edge $e=x y$ is not identified uniquely by the pair $(x, y)$ or $(y, x)$, we define directed edges as triples:
$$
\vec{E}:={(e, x, y) \mid e \in E ; x, y \in V ; e=x y} .
$$
Thus, an edge $e=x y$ with $x \neq y$ has the two directions $(e, x, y)$ and $(e, y, x)$; a loop $e=x x$ has only one direction, the triple $(e, x, x)$. For given $\vec{e}=(e, x, y) \in \vec{E}$, we set $\bar{e}:=(e, y, x)$, and for an arbitrary set $\vec{F} \subseteq \vec{E}$ of edge directions we put
$$
\bar{F}:={\bar{e} \mid \vec{e} \in \vec{F}}
$$
Note that $\vec{E}$ itself is symmetrical: $\bar{E}=\vec{E}$. For $X, Y \subseteq V$ and $\vec{F} \subseteq \vec{E}$, define
$$
\vec{F}(X, Y):={(e, x, y) \in \vec{F} \mid x \in X ; y \in Y ; x \neq y},
$$
abbreviate $\vec{F}({x}, Y)$ to $\vec{F}(x, Y)$ etc., and write
$$
\vec{F}(x):=\vec{F}(x, V)=\vec{F}({x}, \overline{{x}}) .
$$
Here, as below, $\bar{X}$ denotes the complement $V \backslash X$ of a vertex set $X \subseteq V$. Note that any loops at vertices $x \in X \cap Y$ are disregarded in the definitions of $\vec{F}(X, Y)$ and $\vec{F}(x)$.

Let $H$ be an abelian semigroup, ${ }^2$ written additively with zero 0 . Given vertex sets $X, Y \subseteq V$ and a function $f: \vec{E} \rightarrow H$, let
$$
f(X, Y):=\sum_{\vec{e} \in \vec{E}(X, Y)} f(\vec{e})
$$

图论代考

数学代写|图论作业代写Graph Theory代考|Perfect graphs

正如第5.2节所讨论的，高色数可能作为一种纯粹的全局现象出现:即使一个图有很大的周长，因此局部看起来像一棵树，它的色数可能是任意高的。由于这种“全局依赖”显然很难处理，人们可能会对不发生这种现象的图感兴趣，即只有在存在局部原因的情况下，其色数才高。
在我们明确这一点之前，让我们注意图$G$的两个定义。最大的整数$r$使得$K^r \subseteq G$是$G$的团数$\omega(G)$，最大的整数$r$使得$\overline{K^r} \subseteq G$(诱导)是$G$的独立数$\alpha(G)$。显然是$\alpha(G)=\omega(\bar{G})$和$\omega(G)=\alpha(\bar{G})$。
如果每个诱导子图$H \subseteq G$都有色数$\chi(H)=\omega(H)$，即$\omega(H)$颜色的平凡下界总是足以为$H$的顶点上色，则称为完美图。因此，虽然证明形式为$\chi(G)>k$的断言通常是困难的，即使在原则上，对于给定的图$G$，它总是可以通过简单地展示一些$K^{k+1}$子图作为具有$k$颜色的不可着色性的“证书”来完成。

乍一看，完美图类的结构似乎有些做作:虽然它在诱导子图下是封闭的(如果仅通过显式定义)，但它在取一般子图或超图时并不封闭，更不用说子图了(例子?)然而，完美性在图论中是一个重要的概念:图的几个基本类是完美的(似乎是侥幸)，这一事实可能是这一点的表面迹象。 ${ }^3$

那么，什么样的图表是完美的呢?例如，二部图。不那么平凡的是，二部图的补也是完美的，这一事实等价于König的对偶定理2.1.1(练习36)。所谓的可比性图是完美的，区间图也是如此(参见练习);这两种情况在许多应用程序中都会出现。

为了详细地研究至少一个这样的例子，我们在这里证明弦图是完美的:一个图是弦图(或三角图)，如果它的每个长度至少为4的环都有一个弦，即，如果它不包含除三角形以外的诱导环。

为了证明弦图是完美的，我们将首先描述弦图的结构。如果$G$是一个具有诱导子图$G_1, G_2$和$S$的图，例如$G=G_1 \cup G_2$和$S=G_1 \cap G_2$，我们说$G$是由$G_1$和$G_2$通过沿着$S$粘贴在一起而产生的。

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

在流动的背景下，我们必须能够谈论边缘的“方向”。由于在多图$G=(V, E)$中，边$e=x y$不是由$(x, y)$或$(y, x)$对唯一标识的，因此我们将有向边定义为三元组:
$$
\vec{E}:={(e, x, y) \mid e \in E ; x, y \in V ; e=x y} .
$$
因此，具有$x \neq y$的边$e=x y$具有$(e, x, y)$和$(e, y, x)$两个方向;一个循环$e=x x$只有一个方向，即三重$(e, x, x)$。对于给定的$\vec{e}=(e, x, y) \in \vec{E}$，我们设置$\bar{e}:=(e, y, x)$，对于任意的边方向集$\vec{F} \subseteq \vec{E}$，我们设置
$$
\bar{F}:={\bar{e} \mid \vec{e} \in \vec{F}}
$$
注意$\vec{E}$本身是对称的:$\bar{E}=\vec{E}$。对于$X, Y \subseteq V$和$\vec{F} \subseteq \vec{E}$，定义
$$
\vec{F}(X, Y):={(e, x, y) \in \vec{F} \mid x \in X ; y \in Y ; x \neq y},
$$
将$\vec{F}({x}, Y)$缩写为$\vec{F}(x, Y)$等，并写上
$$
\vec{F}(x):=\vec{F}(x, V)=\vec{F}({x}, \overline{{x}}) .
$$
下面，$\bar{X}$表示顶点集$X \subseteq V$的补$V \backslash X$。注意，在$\vec{F}(X, Y)$和$\vec{F}(x)$的定义中，顶点$x \in X \cap Y$处的任何循环都将被忽略。

设$H$是一个阿贝尔半群，${ }^2$与0相加。给定顶点集$X, Y \subseteq V$和函数$f: \vec{E} \rightarrow H$，设
$$
f(X, Y):=\sum_{\vec{e} \in \vec{E}(X, Y)} f(\vec{e})
$$

统计代写请认准statistics-lab™. statistics-lab™为您的留学生涯保驾护航。

如果你也在 怎样代写图论Graph Theory 这个学科遇到相关的难题，请随时右上角联系我们的24/7代写客服。图论Graph Theory有趣的部分原因在于，图可以用来对某些问题中的情况进行建模。这些问题可以在图表的帮助下进行研究(并可能得到解决)。因此，图形模型在本书中经常出现。然而，图论是数学的一个领域，因此涉及数学思想的研究-概念和它们之间的联系。我们选择包含的主题和结果是因为我们认为它们有趣、重要和/或代表主题。

图论Graph Theory通过熟悉许多过去和现在对图论的发展负责的人，可以增强对图论的欣赏。因此，我们收录了一些关于“图论人士”的有趣评论。因为我们相信这些人是图论故事的一部分，所以我们在文中讨论了他们，而不仅仅是作为脚注。我们常常没有认识到数学是一门有生命的学科。图论是人类创造的，是一门仍在不断发展的学科。

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

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

An embedding in the plane, or planar embedding, of an (abstract) graph $G$ is an isomorphism between $G$ and a plane graph $H$. The latter will be called a drawing of $G$. We shall not always distinguish notationally between the vertices and edges of $G$ and of $H$. In this section we investigate how two planar embeddings of a graph can differ.

How should we measure the likeness of two embeddings $\rho: G \rightarrow H$ and $\rho^{\prime}: G \rightarrow H^{\prime}$ of a planar graph $G ?$ An obvious way to do this is to consider the canonical isomorphism $\sigma:=\rho^{\prime} \circ \rho^{-1}$ between $H$ and $H^{\prime}$ as abstract graphs, and ask how much of their position in the plane this isomorphism respects or preserves. For example, if $\sigma$ is induced by a simple rotation of the plane, we would hardly consider $\rho$ and $\rho^{\prime}$ as genuinely different ways of drawing $G$.

So let us begin by considering any abstract isomorphism $\sigma: V \rightarrow V^{\prime}$ between two plane graphs $H=(V, E)$ and $H^{\prime}=\left(V^{\prime}, E^{\prime}\right)$, with face sets $F(H)=: F$ and $F\left(H^{\prime}\right)=: F^{\prime}$ say, and try to measure to what degree $\sigma$ respects or preserves the features of $H$ and $H^{\prime}$ as plane graphs. In what follows we shall propose three criteria for this in decreasing order of strictness (and increasing order of ease of handling), and then prove that for most graphs these three criteria turn out to agree. In particular, applied to the isomorphism $\sigma=\rho^{\prime} \circ \rho^{-1}$ considered earlier, all three criteria will say that there is essentially only one way to draw a 3-connected graph.

Our first criterion for measuring how well our abstract isomorphism $\sigma$ preserves the plane features of $H$ and $H^{\prime}$ is perhaps the most natural one. Intuitively, we would like to call $\sigma$ ‘topological’ if it is induced by a homeomorphism from the plane $\mathbb{R}^2$ to itself. To avoid having to grant the outer faces of $H$ and $H^{\prime}$ a special status, however, we take a detour via the homeomorphism $\pi: S^2 \backslash{(0,0,1)} \rightarrow \mathbb{R}^2$ chosen in Section 4.1: we call $\sigma$ a topological isomorphism between the plane graphs $H$ and $H^{\prime}$ if there exists a homeomorphism $\varphi: S^2 \rightarrow S^2$ such that $\psi:=\pi \circ \varphi \circ \pi^{-1}$ induces $\sigma$ on $V \cup E$. (More formally: we ask that $\psi$ agree with $\sigma$ on $V$, and that it map every plane edge $x y \in H$ onto the plane edge $\sigma(x) \sigma(y) \in$ $H^{\prime}$. Unless $\varphi$ fixes the point $(0,0,1)$, the map $\psi$ will be undefined at $\pi\left(\varphi^{-1}(0,0,1)\right)$.)

数学代写|图论作业代写Graph Theory代考|Planar graphs: Kuratowski’s theorem

A graph is called planar if it can be embedded in the plane: if it is isomorphic to a plane graph. A planar graph is maximal, or maximally planar, if it is planar but cannot be extended to a larger planar graph by adding an edge (but no vertex).

Drawings of maximal planar graphs are clearly maximally plane. The converse, however, is not obvious: when we start to draw a planar graph, could it happen that we get stuck half-way with a proper subgraph that is already maximally plane? Our first proposition says that this can never happen, that is, a plane graph is never maximally plane just because it is badly drawn:
Proposition 4.4.1.
(i) Every maximal plane graph is maximally planar.
(ii) A planar graph with $n \geqslant 3$ vertices is maximally planar if and only if it has $3 n-6$ edges.
Proof. Apply Proposition 4.2.8 and Corollary 4.2.10.

Which graphs are planar? As we saw in Corollary 4.2.11, no planar graph contains $K^5$ or $K_{3,3}$ as a topological minor. Our aim in this section is to prove the surprising converse, a classic theorem of Kuratowski: any graph without a topological $K^5$ or $K_{3,3}$ minor is planar.

Before we prove Kuratowski’s theorem, let us note that it suffices to consider ordinary minors rather than topological ones:

Lemma 4.4.2. A graph contains $K^5$ or $K_{3,3}$ as a minor if and only if it contains $K^5$ or $K_{3,3}$ as a topological minor.

Proof. By Proposition 1.7.2 it suffices to show that every graph $G$ $(1.7 .2)$ with a $K^5$ minor contains either $K^5$ as a topological minor or $K_{3,3}$ as a minor. So suppose that $G \succcurlyeq K^5$, and let $K \subseteq G$ be minimal such that $K=M K^5$. Then every branch set of $K$ induces a tree in $K$, and between any two branch sets $K$ has exactly one edge. If we take the tree induced by a branch set $V_x$ and add to it the four edges joining it to other branch sets, we obtain another tree, $T_x$ say. By the minimality of $K, T_x$ has exactly 4 leaves, the 4 neighbours of $V_x$ in other branch sets (Fig. 4.4.1).

图论代考

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

(抽象)图$G$的平面嵌入或平面嵌入是$G$与平面图$H$之间的同构。后者将被称为$G$的绘图。我们并不总是用符号来区分$G$和$H$的顶点和边。在本节中，我们研究一个图的两个平面嵌入是如何不同的。

我们应该如何测量平面图形的两个嵌入$\rho: G \rightarrow H$和$\rho^{\prime}: G \rightarrow H^{\prime}$的相似性$G ?$一个明显的方法是考虑$H$和$H^{\prime}$之间的规范同构$\sigma:=\rho^{\prime} \circ \rho^{-1}$作为抽象图形，并询问它们在平面上的同构尊重或保留了多少位置。例如，如果$\sigma$是由平面的简单旋转引起的，我们几乎不会认为$\rho$和$\rho^{\prime}$是绘制$G$的真正不同的方法。

因此，让我们首先考虑两个平面图形$H=(V, E)$和$H^{\prime}=\left(V^{\prime}, E^{\prime}\right)$之间的抽象同构$\sigma: V \rightarrow V^{\prime}$，比如面集$F(H)=: F$和$F\left(H^{\prime}\right)=: F^{\prime}$，并尝试测量$\sigma$在多大程度上尊重或保留了$H$和$H^{\prime}$作为平面图形的特征。在接下来的内容中，我们将按照严格程度的递减顺序(以及易处理程度的递增顺序)提出三条准则，然后证明对于大多数图，这三条准则是一致的。特别是，应用于前面考虑的同构$\sigma=\rho^{\prime} \circ \rho^{-1}$，所有三个标准都表明，实际上只有一种方法可以绘制3连通图。

我们衡量抽象同构$\sigma$在多大程度上保留了$H$和$H^{\prime}$的平面特征的第一个标准可能是最自然的标准。直观地说，如果$\sigma$是由平面$\mathbb{R}^2$到自身的同胚引起的，我们就把它称为“拓扑的”。然而，为了避免不得不赋予$H$和$H^{\prime}$的外表面一个特殊的地位，我们绕道通过4.1节中选择的同胚性$\pi: S^2 \backslash{(0,0,1)} \rightarrow \mathbb{R}^2$:我们称$\sigma$为平面图$H$和$H^{\prime}$之间的拓扑同构，如果存在一个同胚性$\varphi: S^2 \rightarrow S^2$，使得$\psi:=\pi \circ \varphi \circ \pi^{-1}$在$V \cup E$上诱导出$\sigma$。(更正式地说:我们要求$\psi$同意$V$上的$\sigma$，并且它将每个平面边$x y \in H$映射到平面边$\sigma(x) \sigma(y) \in$$H^{\prime}$上。除非$\varphi$固定了$(0,0,1)$点，否则映射$\psi$在$\pi\left(\varphi^{-1}(0,0,1)\right)$处将是未定义的。)

数学代写|图论作业代写Graph Theory代考|Planar graphs: Kuratowski’s theorem

如果一个图可以嵌入到平面中，如果它与一个平面图同构，则称为平面图。如果平面图是平面的，但不能通过添加边(但没有顶点)扩展为更大的平面图，则该平面图是最大平面。

最大平面图的绘制显然是最大平面。然而，相反的情况并不明显:当我们开始画一个平面图时，我们会不会在画到一半的时候被一个已经是最大平面的适当子图卡住了?我们的第一个命题是，这种情况永远不会发生，也就是说，一个平面图形永远不会因为画得不好而成为最大平面;
提案4.4.1。
(i)每个最大平面图都是最大平面。
(ii)有$n \geqslant 3$个顶点的平面图当且仅当它有$3 n-6$条边时才是最大平面。
证明。应用命题4.2.8和推论4.2.10。

哪些图形是平面的?正如我们在推论4.2.11中看到的，没有平面图包含$K^5$或$K_{3,3}$作为拓扑次元。本节的目的是证明一个惊人的逆定理，库拉托夫斯基的一个经典定理:任何没有拓扑$K^5$或$K_{3,3}$次元的图都是平面的。

在我们证明Kuratowski定理之前，让我们注意到，考虑普通次子而不是拓扑次子就足够了:

引理4.4.2。当且仅当图中包含$K^5$或$K_{3,3}$作为拓扑次元时，图中包含$K^5$或$K_{3,3}$作为次元。

证明。根据命题1.7.2，足以表明每个具有$K^5$次元的图$G$$(1.7 .2)$都包含$K^5$作为拓扑次元或$K_{3,3}$作为次元。假设$G \succcurlyeq K^5$，让$K \subseteq G$最小使得$K=M K^5$。那么$K$的每个分支集都在$K$中引出一棵树，并且在任意两个分支集$K$之间只有一条边。如果我们取一个分支集$V_x$生成的树，并加上将它与其他分支集连接起来的四条边，我们就得到了另一棵树$T_x$。根据极小性，$K, T_x$恰好有4个叶子，那么$V_x$在其他分支集中的4个邻居(图4.4.1)。

统计代写请认准statistics-lab™. statistics-lab™为您的留学生涯保驾护航。