graph - How to find maximum induced subgraph H of G such that each vertex in H has degree ≥ k

Here is an excise for graph.

Given an undirected graph G with n vertices and m edges, and an integer k, give an O(m + n) algorithm that finds the maximum induced subgraph H of G such that each vertex in H has degree ≥ k, or prove that no such graph exists. An induced subgraph F = (U, R) of a graph G = (V, E) is a subset of U of the vertices V of G, and all edges R of G such that both vertices of each edge are in U.

My initial idea is like this:

First, this excise actually asks that we have all vertices S whose degrees are bigger than or equal to k, then we remove vertices in S who don't have any edge connected to others. Then the refined S is H, in which all vertices have degree >= k and the edges between them is R.

In addition, it asks O(m+n), so I think I need to a BFS or DFS. Then I get stuck.

In BFS, I can know the degree of a vertex. But once I get the degree of v (a vertex), I don't know other connected vertices except for its parent. But if the parent doesn't have degree >= k, I can't eliminate v as it may still be connected with others.

Any hints?

Edit:

According to the answer of @Michael J. Barber, I implemented it and update the code here:

Can anyone have a look at the key method of the codes public Graph kCore(Graph g, int k)? Do I do it right? Is it O(m+n)?

class EdgeNode {
   EdgeNode next;
   int y;
}

public class Graph {
   public EdgeNode[] edges;
   public int numVertices;

   public boolean directed;

   public Graph(int _numVertices, boolean _directed) {
      numVertices = _numVertices;
      directed = _directed;
      edges = new EdgeNode[numVertices];
   }

   public void insertEdge(int x, int y) {
      insertEdge(x, y, directed);
   }

   public void insertEdge(int x, int y, boolean _directed) {
      EdgeNode edge = new EdgeNode();
      edge.y = y;
      edge.next = edges[x];