given a undirected graph ( n nodes , m edges ) , find minimum no. of nodes to remove for making graph completely disconnected ?

constraints — n upto 1000

A greedy way could be start removing the maximum degree nodes untill graph becomes disconnected, is there a proof it would work ?

also i think its related to menger's algorithm , but that gives vertex cut for making 2 nodes disconnected , here we have to disconnect all nodes from each other..

you have been given tree, find a shortest path to travel from 1 to N, such that you visits some given set of nodes in your path from 1 to N. you are allowed to visit same node multiple times.

eg — N = 5

      1  
    /  \ 
  2     3
      /   \ 
    4      5

node_to_visit_in_path = { 2 ,4 }

solution — 6 ( 1 -> 2 -> 1 -> 3 -> 4 -> 3 -> 5)

CONSTRAINTS; 
N UPTO ( 2 * 1e5 ) 
size of {node_to_visit_in_path}  : upto N-1

is this a famous kind of problem ?, i think similar problem i have see somewhere.