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

Synonymous with valence and degree. There are some unrelated things also called 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({\sc v})$ is used for the valency of vertex ${\sc 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 $\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\ge3$ these structures start getting more interesting. 3-valent (or trivalent) graphs are also known as cubic graphs.

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