For open-edge sets in a fixed finite graph, including isolated graph vertices in , one has . Incidence-vector spans have rank ; their union span is the sum of the two spans, while the intersection-edge span is contained in the intersection of spans. The vector-space dimension formula for a sum of subspaces proves submodularity of , equivalently supermodularity of .
A tree component is a graph component whose induced graph is a tree. A tree component with vertices has exactly edges.
The largest graph component is one with the most vertices. Ties may be broken arbitrarily; records the order, which is unaffected by the tie. For a sequence of random graphs, the size of its giant component is a central observable.
Articles by others on the same topic
In graph theory, a **component** (or connected component) of a graph refers to a maximal subgraph in which any two vertices are connected to each other by paths, and which is connected to no additional vertices in the supergraph. In simpler terms, it is a subset of the graph in which there is a path between every pair of vertices, and any vertex not included in this subset cannot be reached from any vertex in the subset.