# valency

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

Synonymous with and . 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(\hbox{\sc 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 $\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\geqslant 3$ 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.

Title valency Valency 2013-03-22 15:10:17 2013-03-22 15:10:17 marijke (8873) marijke (8873) 6 marijke (8873) Definition msc 05C40 valence degree $\rho$-valent trivalent graph cubic graph regular regular graph