edited by
375 views
4 votes
4 votes

Let $\text{G}$ be a simple graph where $\text{V(G)} = \{1, 2, \dots , 100\}$ and there is an edge between two distinct vertices $a$ and $b$ iff $a$ divides $b.$
Which of the following statements are true for $\text{G}?$

  1. The maximum degree of $\text{G}$ is $50.$
  2. The minimum degree of $\text{G}$ is $1.$
  3. $\text{G}$ is connected.
  4. The diameter of $\text{G}$ is $6.$
edited by

1 Answer

6 votes
6 votes
Clearly, any prime between $50$ and $100$ can only be adjacent to vertex $1$ and hence has degree $1.$ Also, every vertex has degree at least $1$ since vertex $1$ is a neighbour of everyone. This also implies that $1$ has the highest degree of $100-1.$
Diameter is $2$ because from vertex to any other vertex, we can have a path of length $2$ via vertex $1.\; \text{G}$ is connected because vertex $1$ is adjacent to everyone.
Answer:

Related questions