In order to do this, you need high degree nodes in your initial network: since you do not add anything, degree may only decrease, and you want high degree nodes in the end.
Now, assume your initial random network indeed has high degree nodes. Since it is random, choosing random links in it will often lead to high-degree extremities. Indeed, the probability to pick a degree $k$ extremity when you choose a link at random is proportional to $k$.
This property underlies the works conducted to estimate bias in internet measurements. Several works show that power-law networks may indeed be obtained from initially random networks, for instance by taking a BFS tree.
See e.g. On the Bias of Traceroute Sampling; or, Power-law Degree Distributions in Regular Graphs for a formal analysis published in STOC and Journal of the ACM, as well as Relevance of Massively Distributed Explorations of the Internet Topology: Qualitative Results for an experimental work published in INFOCOM and Journal of Computer Networks.