All Homework

Homework 1

Problem 1.2.1.11 (a) and (b) on page 21

Homework 2

1. I asked chatGPT to solve Problem 1.2.1.11a from the book. Here is the conversation:
   

   Asked: Prove that if G is a connected graph and diam(G)>=3, then the complement of G is connected.
   Answer: The complement of a graph G, denoted by G', is a graph with the same set of vertices as G, but with an edge between two vertices if and only if there is no edge between them in G. To prove that the complement of a connected graph G with diameter greater than or equal to 3 is connected, we will use contrapositive proof. We will assume that G' is not connected, and show that this leads to a contradiction with the assumption that G is connected with a diameter greater than or equal to 3. Suppose G' is not connected. Then there exist two non-empty, proper, and disjoint subsets of vertices A and B of G such that there is no edge between any vertex in A and any vertex in B in G'. This means that there is an edge between every vertex in A and every vertex in B in G. Since G is connected, there exists a path between any two vertices in G. In particular, there must exist a path between a vertex in A and a vertex in B in G. But this means that the diameter of G is less than 3, which contradicts the assumption that the diameter of G is greater than or equal to 3. Therefore, G' must be connected.

   1. How did it do? Is it a valid proof? Is it well written? What would make it better?
   2. Write up a proof of your own, using the ideas from this proof and your own ideas as appropriate. Your goal is to be as clear and concise as possible.
   
   
2. I asked chatGPT to solve Problem 1.2.1.11b from the book. Here is the conversation:
   

   Asked: Prove that if the diam(G)>=3, then diam(complement G)<=3
   Answer: To prove that if the diameter of a graph G, denoted by diam(G), is greater than or equal to 3, then the diameter of the complement of G, denoted by diam(G'), is less than or equal to 3, we will again use contrapositive proof. We will assume that diam(G') is greater than 3, and show that this leads to a contradiction with the assumption that diam(G) is greater than or equal to 3. Suppose diam(G') is greater than 3. Then there exist two vertices u and v in G' such that the distance between them, denoted by dist(u,v), is greater than 3. In the complement of G, this means that there is no path between u and v in G that has length less than or equal to 3. But this means that there exists a path between u and v in G that has length greater than or equal to 4. This means that the diameter of G, diam(G), is greater than or equal to 4 which contradicts the assumption that diam(G) is greater than or equal to 3. Therefore, diam(G') must be less than or equal to 3.

   1. How did it do? Is it a valid proof? Is it well written? What would make it better?
   2. Write up a proof of your own, using the ideas from this proof and your own ideas as appropriate. Your goal is to be as clear and concise as possible.
   
   

Homework 3

Write a complete proof for problem 1.4.2.5.
Hint: Let v be an arbitrary vertex with degree d and consider the edges (v,v_i) for i=1,...d, where v_i are the neighbors of v. If each of these edges are on an odd number of cycles, you should be able to argue that d is even, at which point we use a theorem from the book to conclude the graph is Eulerian.

Homework 4

• 1.5.2.4
• 1.5.2.10 (NOTE: This problem has a typo. It should say "Find a 4-regular planar graph with triangular regions, and prove that it is unique."

Homework 5

1. Do 1.6.4.3 part 2 (Theorem 1.49 part 2)
   Hint: Start with K_n and use Theorem 1.48 repeatedly.
2. Do 1.6.4.3 part 3 (Theorem 1.49 part 3)
   Hint: Use induction on the number of edges along with the same idea as part 2. (There may be another/simpler way.)
3. Bonus: Prove Theorem 1.49 1-4 together.
(I think a single induction proof can get all 4 parts together.)

Homework 6

3. 1.8.2.5

Homework 7

Do problem 2.2.8.

Homework 8

1. Problem 2.3.3
2. Problem 2.3.11. The ` counts as a symbol.
3. Ask chatGPT or another online AI to solve 2.3.11. Comment on how well it did.

Homework 9

1. Problem 2.5.8
2. Problem 2.5.12 a, b, c

Homework 10

4. Problem 2.6.6.3

Homework 11

1. Do your best attempt at Problem 2.8.1.5. I emailed a photo of some rough work to help (hopefully).