Order, size, complement and independence number

PDF p. 1: Section 2, first paragraph

Let $H=(V(H),E(H))$ be a finite simple graph with at least one vertex. Its order is $\mathrm{\mid }H\mathrm{\mid }:=\mathrm{\mid }V(H)\mathrm{\mid }$, and its size is $\mathrm{\parallel }H\mathrm{\parallel }:=\mathrm{\mid }E(H)\mathrm{\mid }$; here $\mathrm{\mid }A\mathrm{\mid }$ is the number of elements of a finite set $A$.

The complement $\bar{H}$ has vertex set $V(H)$ and edge set $\{\{u,v\}\subseteq V(H):u\mathrm{\ne }v,\{u,v\}\mathrm{\notin }E(H)\}$. Thus two distinct vertices are adjacent in $\bar{H}$ exactly when they are nonadjacent in $H$.

A set $S\subseteq V(H)$ is independent if no two distinct vertices in $S$ are adjacent in $H$. The independence number is $\alpha (H):=\max \{\mathrm{\mid }S\mathrm{\mid }:S\subseteq V(H)\text{ is independent}\}$, the largest cardinality of an independent set.

The graph convention supplies a finite vertex set and an edge set consisting of pairs of distinct vertices. Put $P:=\{\{u,v\}\subseteq V(H):u\mathrm{\ne }v\}$. The set $P$ is finite by A finite set with n elements has exactly C(n, 2) two-element subsets, and 2C(n, 2) = n(n-1), applied to the finite set $V(H)$. Since $E(H)\subseteq P$, A subset of a finite set is finite, with | B| ≤ | A|, and equality holds if and only if B = A shows that $E(H)$ is finite. The finite-cardinality definition therefore gives definite natural numbers for the order and size.

The displayed complement edge set consists precisely of the vertex pairs in $P$ absent from $E(H)$. It is a subset of the finite set $P$, so A subset of a finite set is finite, with | B| ≤ | A|, and equality holds if and only if B = A makes it finite as well. Together with the same nonempty vertex set, it defines the stated finite simple complement graph.

The independence-number definition supplies the maximum: the empty set is independent, and the cardinalities of independent sets form a nonempty bounded set of natural numbers. Consequently $\alpha (H)$ is well-defined.

Graph and colouring conventions

The cardinality | A| of a finite set

Graph isomorphisms, automorphisms and graph complements

Cliques, independent sets, clique number and independence number

A finite set with n elements has exactly C(n, 2) two-element subsets, and 2C(n, 2) = n(n-1)

A subset of a finite set is finite, with | B| ≤ | A|, and equality holds if and only if B = A

The article introduces the symbols for order, size, complement and independence number in the cited paragraph. The explicit set descriptions and well-definedness explanation above make the conventions used here precise.