This is documentation for Mathematica 8, which was
based on an earlier version of the Wolfram Language.
 MATHEMATICA GUIDE Functions »|More About »
Graph Covers and Independent Sets
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