nLab
edge

Contents

Idea

In just about any concept of graph, an edge is something which connects two vertices. In a directed graph an edge is directed, whereas in an undirected graph (the default meaning of “graph” in contemporary combinatorics) it is not.

Terminological remarks

Edges are sometimes called arcs (less common in combinatorics, but sometimes used in other fields) or lines (e.g. Harary, Chapter 2). The latter is now unusual and considered old-fashioned, but survives in the standard technical term line graph? (which is more common than “edge graph” for the same concept). In more specialized contexts other terms are used. For instance, if the graph is the quiver underlying a category, then an edge is a morphism; while if it underlies a simplicial set, then an edge is a 1-dimensional simplex.

Historically, the use of “edge” for connections even in abstract graphs probably derives from the natural connections between graph theory and the theory of polyhedra. One such connection is Steinitz's 1916 theorem? on the one-dimensional skeleta of polyhedra in three-dimensional Euclidean space. However, some deplore the geometric connotations of “edge”, with its geometric connotations of straightness and rigidity.

References

  • Frank Harary: Graph Theory. Addison-Wesley. 1969

Revised on August 3, 2017 11:26:55 by Mike Shulman (76.167.222.204)