MATH 360 Spring 2023Combinatorics and Graph Theory Archived Class

# Homework 2

## Details

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.