---
tag: 91W1A6YHQW
kind: concept
name: Maximal
sources:
  - wikipedia: en:325802@r1373839425
    locator: Glossary of graph theory, section M
    note: adopted
    mention: wikipedia://en/325802#N230
    sections: [Summary]
inventory: [HHKBFFVEH5]
---

## Summary

A subgraph of given graph $G$ is maximal for a particular property if it has that property but no other supergraph of it that is also a subgraph of $G$ also has the same property. That is, it is a maximal element of the subgraphs with the property. For instance, a maximal clique is a complete subgraph that cannot be expanded to a larger complete subgraph. The word "maximal" should be distinguished from "maximum": a maximum subgraph is always maximal, but not necessarily vice versa.

A simple graph with a given property is maximal for that property if it is not possible to add any more edges to it (keeping the vertex set unchanged) while preserving both the simplicity of the graph and the property. Thus, for instance, a maximal planar graph is a planar graph such that adding any more edges to it would create a non-planar graph.