You want to use minimal amount of edges, so we are going to build a tree, because it is the smallest possible connected graph. The longest possible path in any tree is given by the tree diameter. The diameter is twice the distance from the center of the tree to the farthest vertex from the center. In the star graph, the center is 1 edge away from every other vertex, so the diameter and thus the longest path length is clearly 2 edges.