数学代写|MATH2069 Graph Theory

问题 1.

Let $G$ be a $k$-vertex connected graph for some natural number $k \geq 1$. Let $S$ and $T$ be disjoint subsets of vertices in $G$, such that both $S$ and $T$ have at least $k$ vertices. Show that there exist $k$ paths $P_1, P_2, \ldots, P_k$ in $G$ such that two things hold: 1) for each $P_i$, the starting vertex is in $S$ and the end vertex is in $T, 2) V\left(P_i\right) \cap V\left(P_j\right)=\emptyset$ for $i \neq j$ (they cannot have any common vertex – not even the end points).

问题 2.

Suppose $G$ is a simple graph with at least 3 vertices. Show that $G$ is 2 -connected if and only if for every triple of vertices $x, y, z$, there is an $x-z$ path through $y$.

问题 3.

Consider the $n$-CUBE graph (see Problem 4 on HW I). Consider the following two vertices: $x=(0,0, \ldots, 0)$ (all zeroes vector) and $y=(1,1, \ldots, 1)$ (all ones vector). Find a set of vertex disjoint paths of maximum size between $x$ and $y$.

问题 4.

Minimally $k$-connected graphs. A $k$-connected graph $G$ is called minimally $k$-connected, if for every edge $e, G \backslash{e}$ is not $k$-connected. Show that
(i) Show that if $G$ is minimally 2-connected, then the minimum degree of $G$ is exactly 2.
(ii) Show that a minimally 2 -connected graph $G$ with at least 4 vertices has at most $2|V(G)|-$ 4 edges. Construct a minimally 2 connected graph $G$ with at least 4 vertices with exactly $2|V(G)|-4$ edges.

问题 5.

Let $G$ be a 2-connected graph. Let $e=x y$ be any edge in $G$. Show that $G \backslash{e}$ is 2connected if and only if $x$ and $y$ lie on a cycle in $G \backslash{e}$. Conclude that a 2-connected graph is minimally 2-connected if and only if every cycle is an induced subgraph. [Hint: Modify the ear decomposition proof a tiny bit]

问题 6. Suppose $G$ is a simple graph with $n$ vertices and $m$ edges. Put $\alpha=\frac{2 m}{n}$. Prove that the number of vertices with degree more than $2 \cdot \alpha$ is at most $\frac{n}{2}$.