# IndependentVertexSetQ

IndependentVertexSetQ[g,vlist]

yields True if the vertex list vlist is an independent vertex set in the graph g, and False otherwise.

# Details • An independent vertex set is a set of vertices that are never incident to the same edge.
• IndependentVertexSetQ works with undirected graphs, directed graphs, multigraphs, and mixed graphs.

# Examples

open allclose all

## Basic Examples(2)

Test whether a set of vertices is an independent vertex set:

Not all set of vertices are independent vertex sets in a graph:

## Scope(5)

Test undirected graphs:

Directed graphs:

Multigraphs:

Mixed graphs:

IndependentVertexSetQ works with large graphs:

## Applications(2)

Enumerate all independent vertex sets for a cycle graph:

Enumerate all subsets of vertices and select the ones that are independent vertex sets:

Highlight independent vertex sets:

Enumerate all maximum independent vertex sets for a Petersen graph:

Find the size of a maximum independent vertex set:

Enumerate all maximum independent vertex sets:

Highlight maximum independent sets:

## Properties & Relations(4)

A largest independent vertex set can be found using FindIndependentVertexSet:

The complement of an independent vertex set is a vertex cover:

The complement subgraph given by an independent vertex set is complete:

Bipartite graphs have equal-length edge covers and independent vertex sets: