A Question on Notation in Graph Theory

How should we denote the number of vertices and number of edges of a graph G?

Go here for other questions on terminology.

I will soon revise my graph theory textbook Introduction to Graph Theory. First I wanted to know how researchers and users of graph theory answer the question above. Many different notations have been used for these quantities. For example,
number of vertices: |V(G)|, n(G), |G|, v(G), \nu(G)
number of edges: |E(G)|, m(G), ||G||, e(G), \epsilon(G)

In the interest of supporting easier communication, I decided I would change notation for the next edition of my textbook if I found a dominant preference on this in the graph theory community. It turned out that there was such a preference, one quite unexpected by me, because essentially it said "None of the above!" to the options for special notation.

I thank all who sent votes and thought-provoking comments. The experience was quite humbling. I was very surprised by the strong support for |V(G)| and |E(G)|. After the vote totals I discuss the various options and what I will do, incorporating observations made by the voters.

Thanks for voting,
Douglas West

Vote totals

Counting the votes was somewhat difficult, because some respondents did not give a clear answer or introduced other alternatives, so the totals below are approximate. Some respondents took the trouble to vote especially against an alternative; these negative votes are listed in parentheses. I will continue to update totals if further votes come in.

|V(G)|,|E(G)| ..... 56
|V_G|,|E_G| ............. 4 (1)
|V|,|E| ................. 6
v(G),e(G) ........... 7
v,e ....................... 1
\nu(G),\eps(G) ... 3 (1)

n(G),e(G) .................. 5
n,e .............................. 2
n(G),m(G); n_G,m_G ... 9
n,m ............................ 13
|G|,||G|| ..................... 7 (5)
|G|,e(G) ..................... 1

Volker Strehl suggested another possibility that did not occur to me when I proposed the vote, and I held a supplementary vote on it:

#V(G),#E(G): acceptable 18, unacceptable 28
This notation avoids the main objections to the other options. Unfortunately, at present it lacks the "instant recognition" aspect of |V(G)| and |E(G)| that drew many voters to that option. There were also aesthetic objections (some consider this longer, less familiar for students, overly dependent on English, ugly, etc.) Another objection was that we would still want to use |S| for the size of a vertex set S, but I see no difficulty with using this also.

One reason why I like this notation is the way it reads. |V(G)| reads as "size of the vertex set of G", while #V(G) reads as "number of vertices of G", which is what we intend. Otto Smith notes that #V(G)#V(H) is clearer than |V(G)||V(H)|, and the || notation gets worse as the description of the graph inside gets longer.

I personally think this is the best available notation and is consistent with the usage of # in #{x: condition on x}, which I think is increasing. Over the course of a textbook, it would be familiar and transparent. However, clearly too many in the community find it unacceptable.

Past Usage

Thanks to Daniele Degiorgi for the references that were not in my original list:

p, q - Harary/Norman/Cartwright (1965), Harary (1969), Harary/Buckley (1989), Beineke/Wilson (1978, 1983, 1988), Gould (1988)

\nu(G), \epsilon(G) - Bondy/Murty (1976)

v(G), e(G) - Bondy/Murty (2007)

v, e - Wallis (2000)

|G|, e(G) - Bollobas (1978, 1979, 1998)

n, |E| - Gibbons (1985)

n(G), e(G) - West (1996, 2001)

n, m - Chartrand/Lesniak (1979, 1986, 1996, 2005), Buckley/Lewinter (2002), Volkmann (1991, 1996)

|G|, ||G|| - Diestel (1996, 2000, 2005)

No conventional special notation - Konig (1936), Ore (1962), Wagner (1970), Wilson (1972, 1979, 1985, 1996), Biggs (1974, 1993) Trudeau (1976, 1993), Andrasfai (1977, 1991), Carre (1979), Even (1979), Golumbic (1980, 2004), Thulasiraman/Swamy (1981, 1992), Aigner (1984), Tutte (1984), Halin (1989), Halin (1989), Deo (1990), Wilson/Watkins (1990), Clark/Holton (1991), Foulds (1992), Gross/Yellen (1999, 2006), Aldous/Wilson (2000), Merris (2001), Godsil/Royle (2001). Most of these, when needing the number of vertices or number of edges of G, apply |X| to whatever notation X they are using to name the vertex set of edge set of G.

Analysis of Comments

As a textbook author who wants to simplify communication with students over the long course of a book, I sought a notation that would be concise and elegant in this setting and would be widely accepted. Most respondents did not answer from the textbook point of view, since they work more in the context of research papers. Nevertheless, they made points worth considering.

|V(G)| and |E(G)|

Most respondents said they preferred this notation because it is pretty much unambiguous, self-explanatory, and nearly universally understood. This is desirable when looking for a result in a textbook; one does not want to search for definitions of possibly unfamiliar notation. A secondary reason is that this notation avoids most of the disadvantages of the other options. It does not introduce mathematical inconsistencies, and it does not introduce additional notation for students to learn when beginning graph theory.

There are some disadvantages. This notation treats the order and size as the outcome of two-step operations on a graph, rather than as aspects of the graph as simple and fundamental as the maximum degree (some respondents considered this a weak objection). Also, formulas using this notation are a bit cluttered. Some respondents counter the length objection by saying that |V(G)| and |E(G)| will be shortened to |V| and |E|, which I don't think is a good idea.

I think most researchers do not think in the cardinality notation when they work on graph problems. Indeed, many respondents who prefer this option report that they avoid the heaviness of such formulas by using n and m, writing n=|V(G)| and m=|E(G)| or simply reserving these symbols for this purpose. The problem with making a conventional declaration throughout a textbook is precisely the problem that the use of |V(G)| and |E(G)| was intended to avoid. First, it is a local convention that someone consulting the middle of the text cannot be certain of. Second, when there is more than one graph in a discussion, the need to modify n for each graph makes a global convention untenable.

To use the convention without global cement between n and G, one writes sentences like "Let G be a graph with n vertices and m edges" whenever stating a result in terms of these parameters. Harary did this concisely by writing "Let G be a (p,q)-graph", but this convention is rarely used now. One can also use n in a formula about G and then append "where n=|V(G)|".

My second edition already has many exercises that specify G to be an n-vertex graph. Given the lack of mathematical inconsistencies in this approach, the overwhelming support for this option becomes hard to ignore.

In response, I first tried writing a paper without having operators for the order and size of a graph. It was painful. However, after revising the graph theory section of my graduate textbook Combinatorial Mathematics (not yet published) for use in my graduate course this semester, I must say that it is not so bad.

It is true that many more instances of "Let G be an n-vertex graph" must be added. However, the more consistent use of n and m for the order and size of a graph (sharply reducing other uses of these letters) leads to a somehow smoother feel. True, |V(G)| and |E(G)| show up from time to time in formulas when a graph has been discussed with no prior reference to the order or size, or when considering a computation over all subgraphs. However, one can often avoid the cardinality formula by using English and expressions like "letting n=|V(G)|".

The other benefit is that what I tell students in the book will now agree better with actual practice. Most researchers use n and (less frequently) m as a matter of course in discussing a particular graph. A textbook should not simply declare every graph expressed as G to have n vertices, but it can maintain precision in usage while familiarizing students with the habit of using n for the size of the vertex set.

I would have preferred to have simple notations for these as parameters of a graph, but the available concise options all have deficiencies as described below. This election has been a resounding rejection of every one of them. It surprised me, it opened my eyes, and it enabled me to let go of my past notation and consider the alternatives objectively, reaching the conclusion described above.

|V_G| and |E_G|

Respondents who preferred this were in fact addressing a different issue. They object to treating V and E as functions on an input graph. With V_G and E_G, one could suppress the subscript when the graph is understood (as we do with the vertex degree function d_G), obtaining the conventional V and E. Many supporters of |V(G)| and |E(G)| like to do this also, but in the subscript notation it seems more justifiable. However, the meaning in words of V(G) or V_G is "the vertex set OF G". Hence the functional notation fits the meaning. Also, Arthur Hobbs observed that when many graphs G₁,...,G_k are present, the notation V(G_i) is less awkward than V_{G_i}. Finally, V(G) and E(G) are far more widely used than V_G and E_G.

n(G) and m(G)

Like all options using parentheses, these treat the order and size as graph parameters (the result of an evaluation). Unfortunately, it is inconsistent to use n(G) and also use n alone as the number of vertices of a particular graph. Although I previously avoided using n and n(G) together in the same discussion, this conflict still always bothered me. One should not use the same notation as the name of a function and as the value of that function at a single point. Doing so is a common and regrettable abuse of notation in mathematics. I do not say that a graph has maximum degree \Delta or an independent set of size \alpha. To be consistent, I should not use "n-vertex graph" if elsewhere I use "n(G)" to denote the order of an arbitrary graph G.

The notation m(G) suffers the same problem. In addition, sometimes we want to use m as the size of a set of vertices or n as the size of a vertex subset, as in K_n,n, K_m,m, etc. The general K_m,n can be changed to K_r,s, etc. However, there is still good motivation for discussing subgraphs of K_n,n, since these correspond to binary matrices of order n, and their perfect matchings correspond to permutations of [n].

A secondary disadvantage noted by Stephen Hartke is that "m" sounds too much like "n" in a classroom context. Fortunately, we don't need m as often, and I hope that in class it will be easy to add "number of edges" to avoid confusion.

v(G) and e(G)

With this notation, one would avoid the extra step of using cardinality symbols. Also, even though this introduces additional notation, many mathematicians like to use uppercase letters for sets and the corresponding lowercase letters for their sizes. Furthermore, this option permits use of the conventional n and m by writing n=v(G) and m=e(G) without confusion. I have been told that Bondy and Murty use this option in their forthcoming second edition. Wal Wallis uses v and e (but not v(G) and e(G)), noting that v is the letter in design theory that corresponds to the common usage of n in graph theory.

The primary objection to this option is that we want to have v and e available for individual vertices and edges. Although readers could determine the meaning by whether or not the notation is followed by a parenthesis and the name of a graph, many respondents find this multiple meaning of the characters to be a serious deficiency.

\nu(G) and \epsilon(G)

I think Bondy and Murty introduced \nu(G) and \epsilon(G) in their first edition to avoid the disadvantages of n(G),m(G),v(G),e(G) mentioned above. It was serendipitous cleverness that \nu evokes both v and n. Nevertheless, some feel that order and size are too fundamental to have such fancy notation as Greek letters.

Meanwhile, there have been other uses for \nu(G) and \epsilon(G) as parameters, such as crossing number, vertex cover number, matching number, eccentricity, etc. I think these difficulties could be overcome: crossing number is moving to cr(G), for vertex cover I use \beta(G), matching (edge-independence) number should be alpha'(G) by analogy with edge-chromatic number chi'(G), and eccentricity is not needed often.

Of the options in functional form, this is the only one that does not create mathematical inconsistencies with other notational conventions. Unfortunately, this notation did not catch on, especially in computer science. The main objection to using it is that no one uses it now, not even its originators.

|G| and ||G||

This option raised the most passion; supporters are solidly behind it, but it received more flat rejections than any other option. It avoids the difficulty of having multiple meanings for notation within graph theory (almost) and seems convenient. However, a graph is neither a set nor a point in a metric space, so this notation is inconsistent with other mathematics. A more serious source of confusion is that we still need the cardinality symbol. For example, we want to write |N(S)|\ge |S| in discussing Hall's Theorem.

The abuse of notation is perhaps not too bad, since the symbols denote the sizes of two sets that together form G. Kierstead notes that for model theorists a graph G with vertex set V is a model with universe V, and they use |G| for the size of the universe of a model G. In some sense ||G|| would be consistent with this. (He also jokes with his students that the number of faces in a plane graph G could be denoted |||G|||).

On the other hand, |V(G)| and |E(G)| are similar to this and completely clear without being much longer, and some users fear confusion between |G| and ||G||. There have been instances in which ||S|| was used to denote the size of a set S.