A typical graph problem is that of matching different items, such as dates between men and women given preferences or teachers and courses with different preferences. These are all examples of maximum independent edge problems. Similar resource allocation problems are related to all the cover and independent set problems.

Complete Subgraphs

FindClique — find complete subgraphs

CompleteGraphQ — test whether a graph is a complete graph

Vertex Covers

FindVertexCover — find vertex sets that are incident to every edge

VertexCoverQ — test whether a vertex set is a vertex cover

Edge Covers

FindEdgeCover — find edge sets that are incident to every vertex

EdgeCoverQ — test whether an edge set is an edge cover

Independent Vertex Sets

FindIndependentVertexSet — find vertex sets that are never incident to the same edge

IndependentVertexSetQ — test whether a vertex set is an independent vertex set

Independent Edge Sets

FindIndependentEdgeSet — find edge sets ("matchings") that are never incident to the same vertex

IndependentEdgeSetQ — test whether an edge set is an independent edge set