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
|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 |
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.
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.
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.
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.
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.
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.
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.