Homework 5:
7.2.7: Let $x$ and $y$ be vertices of $H$. If both $x$ and $y$ are in $H_1$ or both in $H_2$, then there is path connecting $x$ to $y$ in that piece. So we may assume $x\in H_1$, and $y\in H_2$. Choose $z\in V(H_1)\cap H_2$. There is a path in $H_1$ from $x$ to $z$, and a path in $H_2$ from $z$ to $y$. So we get a walk from $x$ to $y$ in the union, which gives a path.
7.2.9: Let $x$ and $y$ be in different components, and $xy$ an edge. Then there is a path from $x$ to $y$ namely that edge. So $x$ is connected to $y$.
7.2.11: What is the maximum number of edges a disconnected simple graph on $n$ vertices may have? If it has $2$ components, with $k$ vertices and $n-k$ vertices, $1\le k\le n-1$ this graph has at most $\binom{k}{2}+\binom{n-k}{2}$ edges. This quadratic function of $k$ is minimized at $k=n/2$, so the values of $k=1$ and $k=n-1$ give the largest number of vertices which is $\binom{n-1}{2}.$
7.3.5: (a) No. For a simple graph, this would have 7 vertices, and a vertex of degree 0, not connected to
any vertex.
So a degree 6 vertex is impossible.
(b) No. This would have 3 vertices of odd degree, which is impossible.
7.3.9: Suppose that $G$ is not connected, and let $C_1$ and $C_2$ be any two components. The the complement of $G$ contains all edges between vertices of $C_1$ and $C_2$. So if two vertices are in different components, there is a edge connecting them in the complement. If two vertices are in the same component, connect them each to a vertex in another component, giving a path a length 2.
7.3.10: Let $T$ be a spanning tree of $G$. Then $T$ has at least 2 leaves, choose one of them, say $x$. Deleting $x$ and all of $x$'s edges leaves $T-x$, a tree connecting all vertices of $G$ except $x$.
8.1.3: Since $G$ is a tree it is connected, so there is path connecting $a$ to $b$.
Suppose by contradiction, that there are
2 paths $P_1$ and $P_2$ connecting $a$ to $b$. we'll show this
implies $G$ has a cycle which is a contradiction. We can assume that
$a$ $b$, $P_1$, $P_2$ are chosen so that $length(P_1)+length(P_2)$
is minimized.
If $P_1$ and $P_2$ share no vertices other than $a$ and $b$, we create a cycle in $G$ by doing $P_1$
then $P_2$ backwards. If they share another vertex $v$, we choose $v$ to be the last
such vertex on $P_1$. Using $v$ to $b$ on $P_1$ and $P_2$ gives shorter paths from $v$ to $b$.
The second part is clear, the graph is connected with no cycle.
8.5.3: What is the fewest edges a graphs with $n$ vertices and $k$ components may have? Each component has a spanning tree, so the number of edges is at least the number of vertices -1 for each component. Thus the number of edges of the entire graph is at least n-#components: $$ |E| \ge n-(\# components). $$ So if $|E|=m$ this is $$ \# components \ge n-m. $$
8.5.9: Let $P_1:x_0-x_1-\cdots -x_k$ and $P_2:y_0-y_1-\cdots -y_k$ be disjoint paths of maximum distance $k$. We will find a longer path, which is a contradiction. Take any path $P$ connecting a vertex of $P_1$ to a vertex of $P_2.$ Let $z=x_t$ be the last vertex of $P_1$ on $P$, and let $w=y_s$ be the first vertex of $P_2$ after $x$ on $P$. Then the subpath of $P$ connecting $z$ to $w$, call it $Q$, can be used to create a longer path: either $x_0-\cdots - z=x_t-Q-y_{s+1}-\cdots- y_k$ or $x_0-\cdots - z=x_t-Q-y_{s-1}-\cdots- y_0$ or $x_k-\cdots - z=x_t-Q-y_{s+1}-\cdots- y_k$ or $x_k-\cdots - z=x_t-Q-y_{s-1}-\cdots- y_0$.
E1: In the Prufer code we must have $k-1$ 1's. So the answer is $$ \binom{n-2}{k-1} (n-1)^{(n-2)-(k-1)}. $$
E2: These are easy, I did (b) in class.
E3: An element of $A$ has degree $n-k$ while an element of $B$ has degree $k+1$.
Let's verify the matching condition by counting edges from $S\subset A$ to
$R(S)$.
There are $|S|*(n-k)$ edges from $S$ to $R(S).$ This is at most all edges from
$R(S)$, which is $|R(S)|*(k+1).$ So
$$
|S|*(n-k)\le |R(S)|*(k+1),
$$
and since $k+1\le n-k$ we have $|S|\le |R(S)|.$
E4: TRUE: Proof #1: The number of spanning trees is $n^{n-2}$, and each uses $n-1$
edges. Since
each
edge is the same for $K_n$, any particular edge $e$ occurs
$n^{n-2}(n-1)/\binom{n}{2}=2n^{n-
3}$
times.
Proof #2; You can use the Prufer correspondence: the edge 1-2 means that both 1 and 2 cannot
be
leaves until the very end. So vertices 1,2 are never the largest leaf, the last
entry in the Prufer word is either 1 or 2.
E5: The answer is $m^{n-1}*n^{m-1}$. Applying the MatrixTree Theorem this can be done with row operations. The Laplacian matrix is $m+n \times m+n$ in block form, and we cross off the last row and column.
Imagine a $m+n-1 \times m+n-1$ block matrix with an $m\times m$ matrix $n*I$, then a $m\times n-1$ matrix of all -1, next below a $n-1\times m$ matrix of -1, and finally a $n-1\times n-1$ matrix $m*I.$ Our goal is to use row operations to make this matrix upper triangular.
If we add all rows to the first row, the new first row is $(1,1,\cdots, 1, 0,0,\cdots, 0).$ Then adding this new first row to each other row gives an upper triangular matrix whose diagonal entries are 1, n (m-1 times), and m (n-1 times). So the det is $n^{m-1}*m^{n-1}.$