title: graph - How to find maximum induced subgraph H of G such that each vertex in H has degree ≥ k
body: <p>Here is an excise for graph.</p>
  
  <blockquote>
    <p>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. </p>
  </blockquote>
  
  <p>My initial idea is like this:</p>
  
  <p>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.</p>
  
  <p>In addition, it asks O(m+n), so I think I need to a BFS or DFS. Then I get stuck.</p>
  
  <p>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.</p>
  
  <p>Any hints?</p>
  
  <hr>
  
  <h2>Edit:</h2>
  
  <p>According to the answer of @Michael J. Barber, I implemented it and update the code here:</p>
  
  <p><strong>Can anyone have a look at the key method of the codes <code>public Graph kCore(Graph g, int k)</code>? Do I do it right? Is it O(m+n)?</strong></p>
  
  <pre><code>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];
        edges[x] = edge;
        if (!_directed)
            insertEdge(y, x, true);
     }
  
     public Graph kCore(Graph g, int k) {
        int[] degree = new int[g.numVertices];
        boolean[] deleted = new boolean[g.numVertices];
        int numDeleted = 0;
        updateAllDegree(g, degree);// get all degree info for every vertex
  
        for (int i = 0;i &lt; g.numVertices;i++) {
            **if (!deleted[i] &amp;&amp; degree[i] &lt; k) {
             deleteVertex(p.y, deleted, g);
            }**
        }
  
        //Construct the kCore subgraph
        Graph h = new Graph(g.numVertices - numDeleted, false);
        for (int i = 0;i &lt; g.numVertices;i++) {
           if (!deleted[i]) {
             EdgeNode p = g[i];
             while(p!=null) {
                if (!deleted[p.y])
                   h.insertEdge(i, p.y, true); // I just insert the good edge as directed, because i-&gt;p.y is inserted and later p.y-&gt;i will be inserted too in this loop.
                   p = p.next;
                }
             }
           }
        }
  
        return h;
    }
  
    **private void deleteVertex(int i, boolean[] deleted, Graph g) {
       deleted[i] = true;
       EdgeNode p = g[i];
       while(p!=null) {
          if (!deleted[p.y] &amp;&amp; degree[p.y] &lt; k) 
              deleteVertex(p.y, deleted, g);
          p = p.next;
       }
    }**
  
    private void updateAllDegree(Graph g, int[] degree) {
       for(int i = 0;i &lt; g.numVertices;i++) {
           EdgeNode p = g[i];
           while(p!=null) {
              degree[i] += 1;
              p = p.next;
           }
       }
    }
  </code></pre>
  
  <p>}</p>