Find longest path in graph with N nodes and N edges We have given weighted undirected connected graph with $n$ nodes and $n$ edges, we want to find the longest path in it. Note that the path should be in each node at most once. Since the graph has $n$ edges clearly it has exactly 1 cycle, and removing 1 edge from this cycle will lead us to a tree.

Clearly we can iterate over all edges of the cycle and run dijkstra to find this path in tree. But this has complexity of $O(N^2)$ in worse case if the whole graph is cycle. I was thinking that greedy solution that we should remove always the edge with lowest weight that lies on the cycle. How to prove this greedy solution, is it correct at all?
The greedy solution is not correct.

Let me construct a graph with $5$ vertices, $A$, $B$, $C$, $D$, $E$. 

$AB$ is an edge with weight $1$. 

$BC$ is an edge with weight $2$. 

$AC$ is an edge with weight $2$. 

$AD$ is an edge with weight $100$. 

$CE$ is an edge with weight $100$. 

The longest (heaviest) path is $DABCE$ with weight $203$. After removing $AB$, which is the lightest edge of the cycle $ABC$, the longest path is $DACE$ with weight $202$.