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

Proof . (a) Let $G=(V, E)$ be a graph, $A \cup B=V$ a cut of this graph and let $T$ be a spanning tree of $G .$ Let $e=(u, v)$ be the edge of minimum weight that crosses from $A$ to $B$. Suppose now that $T$ does not contain $e .$ Since $T$ is connected, it contains a path $P$ between $u$ and $v,$ and $P$ must contain an edge $f$ that crosses from $A$ to $B$. But $T^{\prime}=T-f+e$ is a tree of smaller weight, which is a contradiction.
(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.

Proof . We construct a new graph $G^{\prime}=\left(V^{\prime}, E^{\prime}\right)$ with edge weight $w^{\prime}: E^{\prime} \rightarrow \mathbb{R}$ such that $V \subseteq V^{\prime}$ $E \subseteq E^{\prime}$ and a minimum weight spanning tree of $G^{\prime}$ restricted to $G$ is a maximum weight forest of $G .$ Let $V^{\prime}=V \cup\{u\}$ where $u$ is a new vertex and let $E^{\prime}=E \cup\{(u, v): v \in V\}$ be the new edge set. Define $w^{\prime}(e)=-w(e)$ for all edges $e \in E$ and $w^{\prime}(e)=0$ otherwise. Let $T$ be a spanning tree of $G^{\prime}$ and $F$ its restriction to $G .$ Then if $F$ is not of maximal weight, there exists an other forest $F^{\prime}$ with higher weight. Adding an edge from $u$ to each connected component of $F^{\prime}$ gives a tree in $G^{\prime}$ whose weight is lower than the weight of $T$. This implies that $T$ was not a minimal weight spanning tree and thus each minimal weight spanning tree of $G^{\prime}$ gives a maximal weight forest in $G$.

Proof . Set $|V(G)|=n$. If the graph is complete then it has a Hamilton cycle. Consider two nonadjacent vertices $u, v$. Remove them to get a graph $G-u-v$ with $n-2$ vertices and $|E(G)|-d(u)-d(v)$ edges. It has at most $\left(\begin{array}{c}n-2 \\ 2\end{array}\right)$ edges, so we have
$$
\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.

Proof .

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$.