How to choose the maximum number of nodes (with constraints) from a graph
Assume the set of nodes have weights $v_1 &lt; v_2 &lt; \dots &lt; v_n$.

Two observations that follow immediately from your restrictions:


Your selection has to be a set of the form $v_i, v_{i+1}, \dots, v_n$.
Every chosen node is neighbour of another chosen node.


That is, we want to find

$\qquad\displaystyle \min \{ i \mid \forall j \geq i\ \exists j' &gt; j\,.\ j \in N(j')\} $

where $N(i)$ denotes the neighbourhood of nodes with (weight-)index $i$.

Therefore, the following algorithm solves the problem in time $O(n \log n)$ (assuming an adjacency matrix):


Sort the nodes by weight.
Choose nodes greedily from the back of the list as long as the new node is neighbour of one of its predecessors (and you have chosen less than $x$).
Output the result.


I'll leave the proofs of correctness and runtime to you.



Now, if weights can be equal we may be able to take some more nodes; if $v_i$ is the first weight we don't pick according to the above algorithm, we have to check all $k$ nodes of weight $v_i$ we have not checked yet, picking as many as we can. This adds a fix-point iteration with at most $k$ iterations running in time $O(k)$ each.

An alternative is to sort the weights in to buckets and pick reachable nodes from the next smallest buckets. Details again left to the reader.