Problem $1$: In class, we saw that trees have several important properties. But what might surprise you is that many of these properties serve as an equivalent definition of a tree! In this problem, you will prove that five separate properties are all equivalent, thus showing that any of these can be used as a definition

of a tree.

We will be using the following five properties:

A : Graph G is acyclic and connected.

B : Graph G is acyclic, and adding an edge between any two non$-$neighbours creates a cycle.

C : Graph G is acyclic, with $|$E$|=|$V $|-1.$

D : For any pair of vertices u and v in the graph G$,$ there is a unique path between u and v$.$

E : Graph G is connected, and deleting any edge makes the graph disconnected.

In this problem, you will show that each of those properties implies the next, proving that they are equivalent.

Note: Each of these parts are independent. If you are stuck at one, we recommend that you try a different one.

a$.$ Prove that A implies B$.$

b$.$ Prove that B implies C$.$

c$.$ Prove that C implies D$.($Hint: Begin by proving that the graph must have a leaf, then use induction to prove the desired result.$)$

d$.$ Prove that D implies E$.($Hint: Consider an arbitrary edge e in the graph, and think about what the unique path between its endpoints must be$.)$

e$.$ Prove that E implies A$.($Hint: Consider the contrapositive: If the graph is connected and has a cycle, what can we conclude?$)$

Problem $2(15$ points$)$: A sequence of integers is called a supercombination for n if for any pair of integers between $1$ and n $($inclusive$),$ that pair appears as two consecutive values in the sequence $($in some order$).$ For example, the following is a supercombination for $4,$ with all the pairs highlighted.

$12314324$

$\{1,2\}\{1,3\}$

$\{1,4\}\{2,3\}\{2,4\}$

$\{3,4\}$

Note that there are exactly n$($n $-1)/(2)$ pairs of integers between $1$ and n$.$ As such, any supercombination must have at least n$($n $-1)/(2)+1$ elements in it$.$

We say that a supercombination is optimal if it has that exact length. For example, the above supercombination is not optimal, as $8>4*(3)/(2)+1=7.$

For which values of n do optimal supercombinations exist?

Problem $3(10$ points$)$: When every vertex in a graph G has degree exactly d$,$ we say that that graph is $$d$-$regular$.$

After learning of some of the neat properties of d$-$regular graphs, Lem E$.$ Hackett is back, and he has a new idea for a result, based on what he$$s seen so far.

For the following, a $$cycle graph$$ is a graph consisting of only a single cycle: There is one cycle in the graph, which also contains all the edges in the graph.

Theorem $1($Lem$$s Theorem$).$ Every $2-$regular simple graph is a cycle graph.

Proof. I prove this by induction. Let P $($n$)$ be $$every $2-$regular simple graph on n vertices is a cycle graph$.$

The smallest $2-$regular simple graph is a triangle, so our base case is n $=3.$ This is also the only $2-$regular simple graph on $3$ vertices, so P $(3)$ is true.

Now, suppose that P $($n$)$ is true. Then every $2-$regular simple graph G on n vertices is a cycle graph. Now, observe that to get to a $2-$regular simple graph on n $+1$ vertices, we have to delete an edge in G$,$ add a new vertex, and connect it to the endpoints of the deleted edge. Let us label these endpoints v$1$ and vn$,$ and the new vertex as v$.$

v$1$ vn $=$ v$1$ vn

v$$

G G$$

As G was a cycle graph, it contains a cycle of the form v$1,$ v$2,...,$ vn$,$ v$1,$ which contains all the edges in the graph. Construct a new cycle, v$1,$ v$2,...,$ vn$,$ v$,$ v$1$ in G$.$ This clearly contains every edge in G$,$ so G$$ must be a cycle graph.

Thus, by induction, all $2-$regular simple graphs are cycles.

a$.$ Is Lem correct? If he is wrong, provide a counterexample.

b$.$ If Lem is right, does his proof still apply if the graphs don$$t have to be simple?

c$.$ If Lem is wrong, what is the issue with his proof?

Extra Credit Problem: Let u and w be vertices in a graph G such that there are two distinct paths from u to w in G$.$ Prove that there must exist a cycle in G$.$

$($Hint: Proving that there is a cyclic walk is not difficult. The hard part is proving that there is a cycle that doesn$$t repeat vertices.$)$