vertexsett

Vertexsett, also known as the vertex set, is a foundational concept in graph theory and related areas. It refers to the collection of all vertices (or nodes) in a graph. A graph is typically described as G = (V, E), where V denotes the vertex set and E denotes the edge set that connects pairs of vertices.

In undirected graphs, edges are unordered pairs of vertices, usually written as {u, v}. In directed graphs (digraphs), edges are ordered pairs, written as (u, v), indicating a direction from u to v. The size of the vertex set, |V|, is called the order of the graph. Each vertex v in V has a degree, deg(v), counting the number of incident edges; in digraphs this is split into in-degree and out-degree.

Vertex sets can be finite or infinite, though most practical discussions focus on finite graphs. Substructures are defined in terms of vertex sets, such as induced subgraphs: for a subset S ⊆ V, the induced subgraph on S has vertex set S and edge set consisting of all edges of G with both endpoints in S. Related concepts include vertex covers, independent sets, and neighborhood sets, all of which are defined as subsets of the vertex set.

Representations of a vertex set often use data structures like adjacency lists or adjacency matrices, which encode how vertices are connected by edges. Algorithms such as breadth-first search and depth-first search operate on the vertex set to traverse or analyze a graph, with time complexity dependent on the size of V and the number of edges.

In geometry and related fields, the term vertex set also describes the set of corner points of polygons or polyhedra, emphasizing that the concept extends beyond abstract graphs to combinatorial geometry.