Saturation (graph theory)

This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these messages) This article relies largely or entirely on a single source. Relevant discussion may be found on the talk page. Please help improve this article by introducing citations to additional sources. Find sources: "Saturation" graph theory – news · newspapers · books · scholar · JSTOR (April 2024) This article may lack focus or may be about more than one topic. Please help improve this article, possibly by splitting the article or organising a disambiguation page. There might be further discussion about this on the talk page. (November 2024) (Learn how and when to remove this message)

Given a graph ${\displaystyle H}$, another graph ${\displaystyle G}$ is ${\displaystyle H}$-saturated if ${\displaystyle G}$ does not contain a (not necessarily induced) copy of ${\displaystyle H}$, but adding any edge to ${\displaystyle G}$ it does. The function ${\displaystyle sat(n,H)}$ is the minimum number of edges an ${\displaystyle H}$-saturated graph ${\displaystyle G}$ on ${\displaystyle n}$ vertices can have.^[1]

In matching theory, there is a different definition. Let ${\displaystyle G(V,E)}$ be a graph and ${\displaystyle M}$ a matching in ${\displaystyle G}$. A vertex ${\displaystyle v\in V(G)}$ is said to be saturated by ${\displaystyle M}$ if there is an edge in ${\displaystyle M}$ incident to ${\displaystyle v}$. A vertex ${\displaystyle v\in V(G)}$ with no such edge is said to be unsaturated by ${\displaystyle M}$. We also say that ${\displaystyle M}$ saturates ${\displaystyle v}$.

• Hall's marriage theorem
• Bipartite matching

This graph theory-related article is a stub. You can help Wikipedia by expanding it.

• v
• t
• e