---
tag: MRDXC2T6YP
kind: concept
name: Dense subgraph
sources:
  - wikipedia: en:32498620@r1369247313
    locator: Dense subgraph
    note: adopted
    mention: wikipedia://en/32498620
    sections: [Summary]
same_as:
  wikidata: Q5259307
  wikipedia: Dense subgraph
inventory: [M2D3NSKM3K]
---

## Summary

In graph theory and computer science, a **dense subgraph** is a subgraph with many edges per vertex. This is formalized as follows: let $G = (V, E)$ be an undirected graph and let $S = (V_{S}, E_{S})$ be a subgraph of $G$. Then the *density* of $S$ is defined to be: