Graph (discrete mathematics): Difference between revisions

Revision as of 01:45, 11 January 2025

Revision as of 00:12, 6 March 2025

Line 164:

Normally, the vertices of a graph, by their nature as elements of a set, are distinguishable. This kind of graph may be called ''vertex-labeled''. However, for many questions it is better to treat vertices as indistinguishable. (Of course, the vertices may be still distinguishable by the properties of the graph itself, e.g., by the numbers of incident edges.) The same remarks apply to edges, so graphs with labeled edges are called ''edge-labeled''. Graphs with labels attached to edges or vertices are more generally designated as ''labeled''. Consequently, graphs in which vertices are indistinguishable and edges are indistinguishable are called ''unlabeled''. (In the literature, the term ''labeled'' may apply to other kinds of labeling, besides that which serves only to distinguish different vertices or edges.)

The [[category theory|category]] of alldirected graphsmultigraphs permitting loops is the [[comma category]] Set ↓ ''D'' where ''D'': Set → Set is the [[functor]] taking a set ''s'' to ''s'' × ''s''.

== Examples ==