I'm Ari Gestetner — a passionate flautist,
music producer, web developer,
CS and Econometrics student
and always looking to learn more.

Question 1

1.a)

![[WhatsApp Image 2024-08-15 at 8.49.32 PM.jpeg|250]]

![[WhatsApp Image 2024-08-15 at 8.49.31 PM (2).jpeg|250]]

![[WhatsApp Image 2024-08-15 at 8.49.31 PM (1).jpeg|250]]

![[WhatsApp Image 2024-08-15 at 8.49.31 PM.jpeg|250]]

![[WhatsApp Image 2024-08-15 at 8.49.30 PM.jpeg|250]]

1.b)

Let be an arbitrary tree with maximum degree 3 Let be the number of vertices in Let be the number of vertices with degree

By the Handshaking Lemma,

Additionally, the number of vertices

Thus we can sub the equation for the number of vertices into the equation for the sum of the degrees

1.c)

Using similar logic to (1.b) we can use the handshaking lemma to find formula for the number of vertices of degree in terms of the number of vertices of degree for all .

Let be the number of vertices of degree Using

and

we get

1.d)

Using the formula from (1.c) we can find the relationship. Since there are only vertices of degree and degree then

So therefore for carbon atoms there are hydrogen atoms

Question 2

There exists a -regular graph on vertices if and only if is even and .

Proof: () Let be a -regular graph on vertices. By the handshaking lemma Therefore, which implies is even Additionally, () We prove that if is even and then there exists a -regular graph by induction on a graph with vertices. Let be the statement "there exists a -regular graph on vertices". We want to show that is true .

Consider the base case when such that is -regular on vertices.

We now assume is true, that is there exists a -regular graph with vertices. Let , , and be distinct edges in . Let be obtained by deleting , , and and introducing new vertices and such that and . Then is -regular with vertices. Hence, is true. Therefore, by MI, holds , meaning that for all even there exists a -regular graph.

Question 3

3.a)

We will prove that for , for every tree with vertices, every graph with minimum degree at least contains a subgraph isomorphic to via induction.

Let be the statement "for every tree with vertices, every graph with minimum degree at least contains a subgraph isomorphic to "

Consider the base case, . All trees with vertices are isomorphic to the tree and . Furthermore, any graph with minimum degree of at least contains an edge connecting nodes and . Thus we can induce a graph , since contains only 2 nodes with a single edge connecting them.

Now assume is true. Let be an arbitrary tree with nodes and a graph with minimum degree . Since every tree has a leaf, we can take some arbitrary leaf with neighbour from and remove it from . Thus, now has nodes and has minimum degree at least (since every node has at least degree). By induction, contains a subgraph isomorphic to . Let be the vertex corresponding to . Since, every has and since then there exists where . Now, let be the tree constructed by adding vertex to and edge . Since and have the same features, therefore, . Thus by mathematical induction, holds

3.b)

We can show that is the best possible minimum degree of graph ()

If the minimum degree of is then we can construct an -regular graph (which has to have even since ) Now let's construct a star with vertices and leaves and a vertex with degree . However, since every vertex in has then there does not exist a vertex with degree thus can't be a subgraph of . Therefore, since for all even there exists a tree and graph where doesn't contain a subgraph isomorphic to then the minimum degree of has to be at least

Question 5

We will prove by induction that if and are spanning trees of connected graph , then can be transformed to through a sequence of intermediate spanning trees of , each arising from the previous tree by deleting one edge and adding one edge.

Let be an arbitrary connected graph Let be spanning trees of

Let Let Let be a spanning tree of with being the number of edges in which aren't in

Let be the statement "there exists a sequence of spanning trees of transforming to each arising from the previous tree by removing an edge then adding an edge"

Consider the base case when Then we have the sequence or , since is the same tree as then there does exist a sequence of spanning trees transforming to (we can remove an edge then add the same edge back). Thus is true.

Now let's assume is true. Meaning that there exists a sequence each arising from the previous by removing an edge then adding an edge. Now if take and an edge from that isn't in the edge set of and delete it. Since every edge in a tree is a bridge, then is a forest with components, and . Since is a spanning tree of and and is connected with no cycles then and such that . Then we can let which is a tree being that there are no cycles in or and they are both separate components so the only path between and is the edge . If then we can choose some edge , remove it then add it back to get . Thus there exists a sequence of spanning trees of transforming to each arising from the previous tree by removing an edge then adding an edge, so therefore by induction, is true .

Now, when forming next tree, we only add an edge which exists in then within steps, . Thus if and are spanning trees of connected graph , then can be transformed to through a sequence of intermediate spanning trees of , each arising from the previous tree by deleting one edge and adding one edge.