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

## 数学代写|图论作业代写Graph Theory代考|k-Edge-Connected

A similar notion with regards to edges exists, where we now look at how many edges need to be removed before the graph is disconnected. Recall that when we remove an edge $e=x y$ from a graph, we are not removing the endpoints $x$ and $y$.

Definition 4.3 A bridge in a graph $G=(V, E)$ is an edge $e$ whose removal disconnects the graph, that is, $G$ is connected but $G-e$ is not. An edge-cut is a set $F \subseteq E$ so that $G-F$ is disconnected.

Clearly every connected graph has an edge-cut since removing all the edges from a graph will result in just a collection of isolated vertices. As with the vertex version, we are more concerned with the smallest size of an edge-cut.
Definition 4.4 We say $G$ is $\boldsymbol{k}$-edge-connected if the smallest edge-cut is of size at least $k$.

Define $\kappa^{\prime}(G)=k$ to be the maximum $k$ such that $G$ is $k$-edgeconnected, that is there exists a edge-cut $F$ of size $k$, yet no edge-cut exists of size $k-1$.

## 数学代写|图论作业代写Graph Theory代考|Whitney’s Theorem

Can you discern any relationship between the vertex and edge connectivity measures? The examples above should demonstrate that these measures need not. be equal, though they can be. How does the minimum degree of a graph play a role in these? Notice how in both $G_2$ and $G_3$ above we found an edge-cut by removing both edges incident to a specific vertex.

Theorem 4.5 (Whitney’s Theorem) For any graph $G, \kappa(G) \leq \kappa^{\prime}(G) \leq$ $\delta(G)$

Proof: Let $G$ be a graph with $n$ vertices and $\delta(G)=k$ and suppose $x$ is a vertex with $\operatorname{deg}(x)=k$. Let $F$ be the set of all edges incident to $x$. Then $G-F$ is disconnected, since $x$ is now isolated, and so $F$ is an edge-cut.
Thus $\kappa^{\prime}(G) \leq k$.
It remains to show that $\kappa(G) \leq \kappa^{\prime}(G)$. If $G=K_n$, then $\delta(G)=n-1$ and $\kappa(G)=n-1$ by definition, and so $\kappa(G)=\kappa^{\prime}(G)$. Otherwise, let $F$ be a minimal edge-cut of $G$ and define $G_1$ and $G_2$ to be the two components of $G-F$. We will consider how these components are related, and in both cases find a cut-set $S$ of size less than that of $F$.

Case 1: Every vertex of $G_1$ is adjacent to every vertex of $G_2$. Then $|F|=\left|G_1\right| \cdot\left|G_2\right| \geq n-1$ since each component has at least one vertex. Since $G \neq K_n$, at least one of $G_1$ and $G_2$, say $G_1$, has a pair of vertices $x$ and $y$ that are not adjacent. Let $S$ be all vertices of $G$ except $x$ and $y$, that is $S=V(G)-{x, y}$. Then $S$ is a cut-set of size $n-2$ and so $\kappa(G) \leq n-2<n-1 \leq \kappa^{\prime}(G)$

## 数学代写|图论作业代写Graph Theory代考|Whitney’s Theorem

myassignments-help数学代考价格说明

1、客户需提供物理代考的网址，相关账户，以及课程名称，Textbook等相关资料~客服会根据作业数量和持续时间给您定价~使收费透明，让您清楚的知道您的钱花在什么地方。

2、数学代写一般每篇报价约为600—1000rmb，费用根据持续时间、周作业量、成绩要求有所浮动(持续时间越长约便宜、周作业量越多约贵、成绩要求越高越贵)，报价后价格觉得合适，可以先付一周的款，我们帮你试做，满意后再继续，遇到Fail全额退款。

3、myassignments-help公司所有MATH作业代写服务支持付半款，全款，周付款，周付款一方面方便大家查阅自己的分数，一方面也方便大家资金周转，注意:每周固定周一时先预付下周的定金，不付定金不予继续做。物理代写一次性付清打9.5折。

Math作业代写、数学代写常见问题

myassignments-help擅长领域包含但不是全部: