19th Ave New York, NY 95822, USA

# Graph Theory代写|图论代写|Hamitonion cycle代写|counting argument代写

(a) Cut Property: the smallest edge crossing any cut must be in all MSTs. Reminder: a cut in a graph $G=(V, E)$ is a partition $A \cup B=V$.
(b) Cycle Property: The largest edge on any cycle is never in any MST.

(b) Let $C$ be a cycle in $G$ and let $e=(u, v)$ be the edge of maximum weight on $C .$ Suppose it is contained in an MST $T$. Deleting $e$ from $T$ we get two connected components $T_{1}, T_{2}$. But the cycle $C$ must contain an edge $f \neq e$ with one end in $T_{1}$ and one end in $T_{2},$ and $T-e+f$ is a tree of smaller weight. Contradiction.

$$\begin{array}{c} \left(\begin{array}{c} n-2 \\ 2 \end{array}\right) \geq|E(G)|-d(u)-d(v)>\left(\begin{array}{c} n-1 \\ 2 \end{array}\right)+1-d(u)-d(v) \\ \Longrightarrow \quad d(u)+d(v)>\left(\begin{array}{c} n-1 \\ 2 \end{array}\right)-\left(\begin{array}{c} n-2 \\ 2 \end{array}\right)+1=n-1 \end{array}$$
Thus the condition of Exercise 2 holds, so $G$ has a Hamilton cycle.

2. Prove that every tournament has an almost central vertex.

Solution: We proceed by induction on the number of vertices. For $n=2,$ it is clear. Let $n>2$ and let $G=(V, A)$ be a tournament on $n$ vertices. Pick a vertex $w$ and consider the tournament $G^{\prime}=G-w$ on the set $V^{\prime}$ of $n-1$ vertices. By induction, there exists an almost central vertex $v$ in $G^{\prime}$. The situation now breaks down in three cases. If there is an arc $a \in A$ directed from $v$ to $w,$ then $v$ is almost central in $G .$ Otherwise, consider the sets $V_{i}^{\prime}:=\left\{u \in V^{\prime} \mid d(v, u)=i\right\}, i=1,2,$ of vertices at distance $i$ of $v .$ Note that because $v$ is almost central in $G^{\prime}$, we have that $\{v\} \cup V_{1}^{\prime} \cup V_{2}^{\prime}=V^{\prime}$. If there is an arc directed from $V_{1}^{\prime}$ to $w,$ the $v$ is almost central in $G .$ Otherwise, all arcs between $w$ and $V_{1}^{\prime}$ are directed from $w$ to $V_{1}^{\prime}$ and there is a directed path of length at most 2 from $w$ to all vertices in $V_{1}^{\prime} \cup V_{2}^{\prime} .$ Furthermore, $w$ and $v$ are connected by an arc from $w$ to $v$. Thus $w$ is almost central in $G$.

abstract algebra代写请认准UpriviateTA. UpriviateTA为您的留学生涯保驾护航。