2
$\begingroup$

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.

  • 0
    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.2012-11-07
  • 0
    so the longest path within a connected, undirected graph differs with every existing graph?2012-11-07
  • 0
    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.2012-11-07
  • 0
    thanks for clearing this up for me. I need it to solve another proof but I think I have a wrong approach.2012-11-07

1 Answers 1