valency

In a graph, multigraph, or pseudograph $G$, the valency of a vertex isthe number of edges attached to it (note that a loop counts twice).

Synonymous with and. There are some unrelated things alsocalled valence; there are of course many things all called degree.

For directed graphs, in- and out- are prefixed to any of the synonyms, to count incoming and outgoing edges separately.

If $\rho (\mathrm{\text{v}})$ is used for the valency of vertex v, the notation $\rho (G)$ (or $\rho$ on its own if there is no scope for confusion) denotes the maximum valency found in graph $G$. Another notation often seen is $\delta (G)$ and $\mathrm{\Delta }(G)$ for lowest and highest valency in $G$ respectively.

If the valency is the same number ($\rho$, say) for all its vertices, $G$ is called regular. More specifically it is called $\rho$-valent or $\rho$-regular. Connected (components of)…

• …0-valent graphs are edgeless vertices,

• …1-valent graphs are pairs of vertices joined by an edge,

• …2-valent graphs are cyclic graphs, i.e. $n$-gons, of various sizes

• From $\rho ⩾3$ these structures start getting more interesting.3-valent (or trivalent) graphs are also known ascubic graphs.

A $\rho$-valent graph with $n$ vertices has $n\rho /2$ edges.