vertexsets

In graph theory and related areas, a vertex set (often denoted V) is the set of all vertices of a graph or other combinatorial structure. If a graph is written as G = (V, E), then V is the vertex set and E is the edge set, consisting of unordered pairs of vertices (for simple graphs). The size of the vertex set is |V|, and the universal set in the context of the graph is V itself.

A vertex set can be any subset of V. For a subset S ⊆ V, one can form the induced subgraph G[S], which contains the vertices in S and all edges of G whose endpoints lie entirely in S. Vertex sets are central to many concepts and problems. Examples of important special vertex sets include a vertex cover, which intersects every edge; an independent set, which contains no two adjacent vertices; and a clique, a subset in which every pair of vertices is connected by an edge.

Beyond simple graphs, the idea of a vertex set appears in hypergraphs (where vertices form the underlying set and hyperedges are subsets of V) and in geometric representations where vertices correspond to points in space. In algorithmic contexts, vertex sets are often maintained as data structures such as lists, bitsets, or hash sets, with operations for membership testing, addition, and removal. They are frequently used as working sets in traversals (for example, marking visited vertices in depth-first or breadth-first search) and as candidates in combinatorial optimization problems.

In summary, the vertex set is a foundational concept representing the elements that serve as the building blocks of a graph or related structure.