数学代写|MA316 Graph Theory

page 165, 6 Let $H$ be an abelian group, $G=(V, E)$ a connected graph, $T$ a spanning tree, and $f$ a map from the orientations of the edges in $E-E(T)$ to $H$ that satisfies (F1). Show that $f$ extends uniquely to a circulation on $G$ with values in $H$.

Solution: Designate a vertex $r$ as a root and orient edges on $T$ from the root toward leaves. Pick a non-root leaf vertex of $T$, called $v_n$, and the edge connecting to $v_n$ in $T$ is called $e_{n-1}$. Let $\vec{e}{n-1}$ be the orientation received from the root toward leaves. Define $$ f\left(\vec{e}{n-1}\right)=-\sum_{\vec{e} \in \vec{E}\left(v_n, V\right), e \neq e_{n-1}} f(\vec{e})
$$
We continue this process to assign values on all edges of $T$. At $i$-th iteration, let $T_i$ be the remaining tree, $v_i$ be a non-root leave of $T_i$, and $e_{i-1}$ be the edge of $T_i$ connecting to $v_i$. We define
$$
f\left(\vec{e}{i-1}\right)=-\sum{\vec{e} \in \vec{E}\left(v_i, V\right), e \neq e_{i-1}} f(\vec{e}) .
$$
Note that the right expression does not contain any edge $e_j$ with $j<i$. Thus $f\left(\vec{e}{i-1}\right)$ is well-defined. When the process is finished, we define the values on all edges of $T$. For $i \geq 2, f\left(v_i, V\right)=1$. We need to show that $f\left(v_1, V\right)=0$ as well. This is because $$ f\left(v_1, V\right)=f(V, V)-\sum{i=2}^n f\left(v_i, V\right)=0 .
$$
Here $f(V, V)=0$ since $f$ satisfies (F1).

page 166, 15 Show that every graph with a Hamilton cycle has a 4flow.

Solution: Assume that graph $H$ has a Hamilton cycle $C$. We only need to prove that $H$ has a $\mathbb{Z}_2 \times \mathbb{Z}_2$-flow. Assign $(0,1)$ to each edge not in $C$. Since it is over the field $\mathbb{Z}_2$, the orientation of edges do not matter. By Problem 1, we can extend this assignment to a circulation of $H$. The only problem is that some edges on $C$ might receive 0 value. But this can be fixed by adding $(1,0)$ to each edge of $C$. Finally we get a nowhere-zero $\mathbb{Z}_2 \times \mathbb{Z}_2$-circulation on $H$. By Tutte’s theorem, $H$ admits a 4 -flow.

page 166, 17 Determine the flow number of $C_5 * K_1$, the wheel with 5 spokes.

Solution: Note that the 5 -wheel is self-dual planar graph. Thus $\phi\left(C_5 *\right.$ $\left.K_1\right)=\chi\left(C_5 * K_1\right)$. Since $\chi\left(C_5\right)=3$, we get $\chi\left(C_5 * K_1\right)=4$. Thus, $\phi\left(C_5 * K_1\right)=4$

page 166, 18 Find bridgeless graph $G$ and $H=G-e$ such that $2<$ $\varphi(G)<\varphi(H)$.

Solution: Let $G$ be the graph obtained by connecting a pair of nonadjacent vertices in the wheel $C_5 * K_1$. Call this edge $e$. Then $H=$ $G-e=C_5 * K_1$. Note that $G$ is still planar graph. One can easy to show the dual of $G$ has chromatic number 3 . Thus $\phi(G)=3$. From the problem 3 , we have shown that $\phi(H)=4$.