# properties of the longest path within a connected graph

I have to identify the longest path of a connected, undirected graph $G=(V,E)$, but I'm currently stuck.

Out of intuition I would say that the longest path in G is $G=|V-1|$ but that doesn't seem to work with every graph.

Happy for any pointers into the right direction.

Sorry for the confusion. I was talking about a connected graph. Wrong translation from my mothertongue.

-
There isn't going to be a nice classification scheme. Just asking whether the graph has a path of length $V-1$ is already difficult. – EuYu Nov 7 '12 at 15:22
so the longest path within a connected, undirected graph differs with every existing graph? – warg Nov 7 '12 at 15:26
Yes. I doubt your question asks you to find the longest path of a graph in general. If you have a bunch of vertices of degree $1$ connected to a central vertex (like in your example) then the longest path is of length $2$. If you have a graph with a Hamiltonian path, then you have a path of $|V|-1$. In general anything in between is possible. – EuYu Nov 7 '12 at 15:30
thanks for clearing this up for me. I need it to solve another proof but I think I have a wrong approach. – warg Nov 7 '12 at 15:36

The Hamilton path problem is NP-complete. Thus, we cannot even reasonably expect to find an efficient algorithm for answering "does the longest path in $G$ have length $|V|-1$?"