From Encyclopedia of Mathematics
Revision as of 19:03, 21 August 2014 by Boris Tsirelson (talk | contribs) (→‎Notation: what exactly is called a graph)
Jump to: navigation, search


The graph notation is not fixed thorough this article.

  • First we are presented with the notation $G\left(V,E\right)$, which uses the symbol $G$ as a functor to create a graph from two sets $V$ and $E$. As a programmer, this notation is nice because it is akin of how object-oriented programming works.
  • Then $H\left(W,I\right)$ implies that $G$ is not a functor at all, but the notation $G(V,E)$ is a mere abbreviation for $G=(V,E)$.
  • Finally $G_1=G(V_1,E_1)$ and $G_2=G(V_2,E_2)$ again uses $G$ as a functor.

Even Boundy & Murty (Graph Theory, Graduate Texts in Mathematics, Springer) which notation has become kind of standard, have some difficulty defining what a graph is from a set theoretical standpoint. They say "a graph $G$ is an ordered pair $\left(V(G), E(G)\right)$ consisting of a set $V(G)$ of vertices and a set $E(G)$, disjoint form $V(G)$, of edges, together with an incidence function $\psi_G$ that associates with each edge of $G$, an unordered pair of (not necessarily distinct) vertices of $G$". So that it is an ordered pair with an extra thing outside of that ordered pair. Even so, we should fix a notation. --M. Abarca (talk) 19:37, 21 August 2014 (CEST)

Indeed... Really, there is no consensus what exactly is called a graph. Graphs (and multigraphs) are defined in terms of vertices and edges. Vertices are a principal base set. One approach ("edges without own identity") treats edges as (ordered or unordered) pairs of vertices. The other approach ("edges with own identity") treats edges as the second principal base set.
"The student of mathematics has to develop a tolerance for ambiguity. Pedantry can be the enemy of insight." (Gila Hanna, a quote).
--Boris Tsirelson (talk) 21:03, 21 August 2014 (CEST)
How to Cite This Entry:
Graph. Encyclopedia of Mathematics. URL: