MathDB

The

\underline{\text{path number}}

of a graph is the minimum number of paths we need to partition the vertices of a graph. Given a connected graph with the independence number

k > 1

, what is the maximum possible value for the path number in this graph? Find the answer in terms of

k

.
The independence number of a graph

<span class='latex-bold'>G</span>

is the maximum possible number

k

, such that there exist

k

pairwise non-adjacent vertices in

<span class='latex-bold'>G</span>

Problem Statement