\paragraph{36.}
For what values of $K_{m, n}$ regular?\newline
\newline
In a complete bipartite graph with sections $m$ and $n$, all vertices in section $m$ have a degree equal to $|n|$, as they connect to all vertices in section $n$, but none in section $m$. By the same vein, all vertices in section n have a degree equal to $|m|$. Thus, for all vertices in the graph to have the same degree, $|n|$ and $|m|$ must be equal.


\paragraph{42.}
If $G$ is a simple graph with 15 edges and $\overline{G}$ has 13 edges, how many vertices does G have?\newline
\newline
Consider the graph $G \cup \overline{G}$. As these two have the same vertices, no vertices are added. $\overline{G}$ has all possible edges that are not in $G$, so the union of $G$ and$\overline{G}$ is a complete graph, and is equivalent to $K_{n}$, where $n$ is the number of vertices in the graph. The number of edges in $K_{n}$ is
\newline\newline
$\frac{n(n-1)}{2}$	%fix this, i only did it because i forgot how to actually do math centering and such
\newline\newline
This comes from the fact that each of the $n$ vertices has degree $(n-1)$; thus, the sum of all the degrees in the graph is $n(n-1)$. However, this counts all the edges twice--once for each of the two vertices connected by each edge, so the expression is halved to account for this. Since we know there are 28 total edges in $G \cup \overline{G}$ (15 in $G$ and 13 in $\overline{G}$), we know that $\frac{n(n-1)}{2} = 28$. Solving this equation for $n$ gives $n = 8$. Thus, $G$ (and $\overline{G}$) have 8 vertices.

\paragraph{22.}
Show that in any simple graph there is a path from any vertex of odd degree to some other vertex of odd degree.\newline
\newline
Any simple graph can be broken up into a number of connected subgraphs. According to the handshaking theorem, these connected subgraphs have a number of edges $e$ divisible by two. It follows from this fact that the connected subgraphs have an even number of vertices with odd degree, as the theorem would be violated if any of the subgraphs had an odd number of vertices with odd degree. (This would make the sum of the vertex degrees odd, which is impossible. For example, $2e = 5$ is impossible in a discrete system). As each connected subgraph has more than one vertex of odd degree, and (by the definition of connected) there is a path between any two vertices in all the connected subgraphs, it follows that there exists a path from any vertex with odd degree to a different vertex with odd degree in any graph.

\paragraph{16.}
Suppose that a connected bipartite planar simple graph has $e$ edges and $v$ vertices. Show that $e \leq 2v - 4$ if $v\leq 3$.\newline
\newline
In a connected simple planar graph, the sum of the degrees of the regions is exactly twice the number of edges in the graph, because each edge occurs on the boundary of a region exactly twice. As the graph is bipartite, each region must have a degree greater than or equal to 4. This comes from the fact that there are two separate sections ($n$ and $m$) in a bipartite graph, and the shortest possible circuit is created as $\{n0, m0, n1, m1, n0\}$, as all vertices in section $n$ are not connected to the other vertices in $n$, and all vertices in section $m$ are not connected to the other vertices in $m$. Thus, $2e = 4r$, or $r \geq \frac{e}{2}$. Using this fact with Euler’s formula ($r = e - v + 2$), we get that $\frac{e}{2} \geq e – v + 2$.
\newline
$v - 2 \geq \frac{e}{2}$
\newline
$e \leq 2v + 4$