A graph consists of a set of nodes (or vertices), some of which are linked to each other by edges (or links).

The edges can be either undirected or directed. A graph in which all edges are undirected is called a undirected graph; if the edges are all directed the graph is called a directed graph. An undirected edge e connecting two nodes v and w is denoted by {v,w} or equivalently {w,v}. A directed edge from node v to node w is denoted by (v,w) which is not equal to (w,v). Here is an example of a graph.

Note that this graph is mixed (i.e. neither undirected nor directed) since it has both undirected and directed edges. For introducing directionality into graphs, cf. polarisation.

A graph is connected if for every pair of nodes in the graph there is a path that connects them.

In the context of stemmatology, a stemma is a particular kind of graph in which the nodes correspond to texts (some of which may be extant and others lost or hypothetical), and the edges indicate relationships between them.

Special cases of graphs include trees and directed acyclic graphs (DAGs).

The word is originally an abbreviation from graphic formula; ultimately it is derived from the Greek verb γράφω 'to write'.

In other languages

DE: Graph
FR: graphe
IT: grafo


  • No labels