MATHEMATICA GUIDE

# 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.

## ReferenceReference

### 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

New to Mathematica? Find your learning path »
Have a question? Ask support »