این سؤال دارای راه حل‌هایی با تحلیل زمانی متفاوت است. ما در زیر به بررسی راه حل، با زمان $O(n^2)$ می‌پردازیم. اما نیم‌نگاهی به راه حل‌های دیگر نیز خواهیم داشت. ضمن اینکه محتوای کلی راه حل‌های مختلف، مبنی بر الگوریتم استقرایی که در زیر ارائه شده‌است می‌باشد.

گراف $G$ به شما داده شده‌است. شما می‌خواهید زیر‌گراف القایی با بیشینه درجه در این گراف را پیدا کنید.

رأسی را که دارای کمترین درجه است در نظر بگیرید. اگر گرافی که در حال حاضر در اختیار دارید را به عنوان جواب در نظر بگیرید، درجه‌ی این گراف، برابر با درجه‌ی این رأس می‌باشد. پس اگر به دنبال پیدا کردن زیر‌گراف القایی، با درجه‌ی بیشتری هستید، به یقین می‌توان گفت که این رأس در آن زیر‌گراف القایی مورد نظر شما وجود نخواهد داشت. پس یا جواب برابر است با زیر‌گراف القایی که در حال حاضر در دست دارید، یا برابر است با جواب سؤال، هنگامی که رأس با کمترین درجه را از گرافتان حذف می‌کنید. این همان حل سؤال به روش استقرایی است.

نکته مهمی که وجود دارد، حذف رأس با کمترین درجه و پیدا کردن این رأس است.
روش اول: روی همه‌ی رأس‌ها پیمایش کرده، سپس رأس با کمترین درجه را حذف کنید و بال‌های مربوط به این رأس را از گراف خود پاک کنید.
روش دوم:‌ روش دیگر می‌تواند این باشد که از داده‌ساختار $heap$ یا $set$ استفاده کنید.
روش سوم: این روش، حل سؤال با $binary \text{ } search$ بر روی جواب است. به این صورت که فرض کنید جواب مسئله برابر با $k$ می‌باشد، سپس رأس‌های با درجه‌ی کمتر از $k$ را درون یک صف بریزید و هر رأسی که درجه‌اش کمتر از $k$ بود را حذف کرده و دوباره رأس‌های با درجه کمتر از $k$ که تازه به وجود آمده‌اند را در صف بریزید. اگر رأسی در نهایت باقی‌ماند، $k$ یک جواب خوب می‌تواند باشد.
روش چهارم: روش آخری که وجود دارد هم، استفاده از روشی مشابه روش $binary \text{ } search$، با این تفاوت که به جای اینکه روی جواب $binary \text{ } search$ بزنید، مسئله را به طور مستقیم حل کنید. یعنی رأس با کمترین درجه را با استفاده از تعدادی صف و مرتب‌سازی‌های خطی، پیدا کنید.
در هر کدام از روش‌های بالا تحلیل‌ها به صورت زیر است:
روش اول: $O(n^2 + m)$
روش دوم و سوم: $O((n + m) \times lgn)$
روش چهارم: $O(n + m)$

maximum_induced_subgraph.cpp

#include <iostream>
using namespace std;
const int maxn = 1000 + 10;
int edge[maxn][maxn];
int mark[maxn], d[maxn];
int n, m;
 
int find_min()
{
  int ret = -1; // we dont know who has the minimum degree
  for(int i=0;i<n;++i)
    if(mark[i] == 0)
      if(ret == -1 || d[ret] > d[i]) // i has less degree than ret
	ret = i;
  return ret;
}
 
void delete_node(int id)
{
  mark[id] = 1; // deleting id
  for(int i=0;i<n;++i)
    d[i] -= edge[id][i];
}
 
int main()
{
  cin >> n >> m;
  for(int i=0;i<m;++i) {
    int u, v;
    cin >> u >> v;
    u--; // we are 0 base
    v--;
    d[u]++;
    d[v]++;
    edge[u][v]++; // multiple edges!!!
    edge[v][u]++;
  }
 
  int ans = 0;
  for(int t=0;t<n;++t) {
    int id = find_min(); // find id of the vertex with minimum degree
    ans = max(ans, d[id]); // this induced subgraph may be the answer
    delete_node(id); // delete this node
  }
 
  cout << ans << endl;
 
  return 0;
}