As much details as possible Please answer only if you are 100% sure points Creat

Question

As much details as possible
Please answer only if you are 100% sure

points Create a simple graph G where the vertices are the integers 1, 2, 3, ... 1000 and where vertex m is connected to vertex n by an edge if and only if m|n or n|m. (Remember: m|n means m is a divisor of n.] It might help to sketch a smaller version of this graph with vertices intergers 1, 2, 3, 4, 5, 6. Prove or disprove: G is connected Find the largest set of vertices you can where every vertex is connected to every other vertex, as in Kn. Find the vertices of largest and smallest degree, and give their degrees.

Explanation / Answer

(a) A graph is connected if it is possible to get from any vertex to any other vertex by traversing the edges. Since 1 divides everything, there is an edge between every vertex and 1. Therefore, we can get from any vertex A to any other vertex B by going from A to 1 and then from 1 to B, so the graph is connected. (b) In order to have all the vertices connceted to one another, every pair of vertices has to divide one another. So the biggest set you're going to be able to make is if you include all of the powers of 2. So in this case, you'd get 1, 2, 4, 8, 16, 32, 64, 128, 256, and 512, for a total of 10 vertices that are all connected with one another. (c) The vertex of largest degree is 1, since it's connected to everything else. So its degree is 999. The vertices with the smallest degrees will be the primes that are bigger than 500. This is because for any prime greater than 500 (like 571), it has no multiples that are smaller than 1000. So the only way it can have an edge with one of the vertices is if the label on that vertex divides it. Since its prime, it can only have an edge with 1. So all of these primes bigger than 500 have degree 1.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.