Graph

A general graph $Γ$ is a pair consisting of a set $Γ 0$ of vertices and a (multi)set $A (Γ) \subseteq V (Γ) \times V (Γ)$ of arcs. #m/def/graph For vertices $𝑣, 𝑤 \in V (Γ)$ , we write $𝑣 \to 𝑤$ iff $(𝑣, 𝑤) \in A (Γ)$ , and $𝑣 \sim 𝑤$ iff both $𝑣 \to 𝑤$ and $𝑤 \to 𝑣$ .

A (simple) graph is a general graph for which $A (Γ)$ is a proper set and is symmetric, and does not contain the diagonal (i.e. $𝑣 ≁ 𝑣$ for all $𝑣 \in V (Γ)$ ). In this case, we refer to edges, defined by

E (Γ) = {{𝑣, 𝑤} : (𝑣, 𝑤) \in A (Γ) \land (𝑤, 𝑣) \in A (Γ)}

Then

the prefix di- indicates that the graph may not be symmetric;
the prefix multi- indicates that $A (Γ)$ is a multiset;
the prefix pseudo- indicates that $A (Γ)$ may include the diagonal (loops).¹

Thus the general case is also referred to as a pseudomultidigraph, which are in many ways equivalent to quivers — see Equivalence of quivers and general graphs,

A structure-preserving map between graphs is a graph homomorphism, and a symmetry of a graph is a graph automorphism.

#state/tidy | #lang/en | #SemBr

Unfortunately this terminology is nonstandard: Normally pseudgraphs are assumed to be multiple as well. ↩

Graph

Footnotes