valency (original) (raw)

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 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 ρ⁢(v) is used for the valency of vertex v, the notation ρ⁢(G) (or ρ on its own if there is no scope for confusion) denotes the maximum valency found in graph G. Another notation often seen is δ⁢(G) and Δ⁢(G) for lowest and highest valency in G respectively.

If the valency is the same number (ρ, say) for all its vertices, G is called regular. More specifically it is called ρ-valent or ρ-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 ρ⩾3 these structures start getting more interesting. 3-valent (or trivalent) graphs are also known ascubic graphs.

A ρ-valent graph with n vertices has n⁢ρ/2 edges.