Graph and colouring conventions

PDF p. 1: Introduction, first paragraph; PDF p. 2: Section 3, complete-graph construction

For this treatment, a graph $H=(V(H),E(H))$ is a finite simple graph with at least one vertex: $V(H)$ is a nonempty finite set and $E(H)$ is a set of two-element subsets of $V(H)$. Two distinct vertices are adjacent when their two-element set is an edge, and are nonadjacent otherwise.

A subgraph $J$ of $G$ has $V(J)\subseteq V(G)$ and $E(J)\subseteq E(G)$. A graph isomorphism is a bijection between vertex sets that preserves and reflects adjacency. A copy of $H$ in $G$ is a subgraph of $G$ isomorphic to $H$; extra edges of $G$ between its vertices need not be edges of the copy. An induced copy is a copy whose edge set contains every edge of $G$ between its vertices, so both adjacency and nonadjacency agree with those in $H$.

For a positive integer $k$, a $k$-colouring of the vertices of $G$ is a function $c:V(G)\to \{1,\dots ,k\}$. It need not use every colour and adjacent vertices may have the same colour. A copy is monochromatic if $c$ has the same value at all its vertices.

For a positive integer $n$, $K_n$ denotes a complete graph on $n$ vertices, meaning that every two distinct vertices are adjacent. An edgeless graph is a graph whose edge set is empty.

The finite-simple-graph convention specifies the vertex and edge sets and makes adjacency a definite condition. The subgraph and isomorphism definitions specify ordinary copies; equivalently, an edge-preserving injection gives a copy on its image vertices with its image edges. Requiring all host edges between those vertices gives the induced-subgraph condition, equivalently the adjacency-reflection condition for an induced embedding. The colouring supplier defines the function and monochromatic predicate without requiring surjectivity or proper colouring. The standard graph supplier specifies complete graphs and empty edge sets. Thus these conventions have definite meanings and are compatible with their suppliers.

A finite simple graph is a finite vertex set together with a set of two-element vertex subsets

Subgraphs, induced subgraphs and spanning subgraphs

Graph isomorphisms, automorphisms and graph complements

Induced embeddings and induced copies of a graph

Empty and complete graphs, complete bipartite graphs, and the convention that Pₙ and Cₙ have n vertices

Unrestricted finite colourings and used palettes

Ordinary embeddings as injections preserving edges

The article explicitly imposes the nonempty-vertex convention and defines a copy as an isomorphic subgraph. Finiteness and simplicity are conventions of this treatment for the article's finite graph constructions; the cited passages do not separately state those axioms.