Question

Width of a tree is defined as the largest distance(number of edges in the shortest path) between any two vertices. What is the smallest possible width of the tree with 100 vertices?

1


2


99


101
1 point
How many complete graphs with at least 1 edge and at most 50 edges are there?

8


9


10


11

Answer 1

(1) Consider a graph called star. This graph is a special kind of tree with one internal node and k leaves and has the smallest possible width. A star $S_{99}$ has 99 edges and 100 vertices and its width is 2.

Answer: 2.

(2) The complete graph $K_n$ on n vertices has $n(n-1)\over2$. In order to answer that question, we need to solve equation for positive integer n:

$$1\le {n(n-1)\over2} \le 50$$ $$2\le n^2 - n \le 100$$

$n \in \{2, 3,4,5,6,7,8,9,10\}$

Therefore, there are 9 complete graphs with at least 1 edge and at most 50 edges ($K_2, K_3, \dots, K_{10}$).

Answer: 9 graphs.