Is the term "n-order graph" commonly used?

Question

Order of a graph is the number of vertices in the graph. I don't know if "n-order graph" is common or standard. For example,

We obtain a 25-order graph with minimum degree 5.

I'm aware that the following statement might also be common.

• We obtain a graph of order 25 with minimum degree 5.
• We obtain a graph on 25 vertices with minimum degree 5.

But just as mentioned in the recent link, the above two expressions could lead to misunderstanding, as it might be interpreted as the graph having 25 vertices with degree 5.

Perhaps the following expression is more common.

• We obtain a 25-vertex graph with minimum degree 5.

However, I still want to ask whether "25-order" is also acceptable.

Answer 1

No, it's not commonly used.

I have never seen it used personally, but that doesn't seem like a sufficient answer, so let me try to add more.

First, I looked through electronic copies of West's Introduction to Graph Theory and Diestel's Graph Theory. Both of these commonly use "graph of order $n$" and its cousins "component of order $n$", "clique of order $n$", "tree of order $n$" where appropriate. If they ever used a variant of "$n$-order" as an adjective, you would expect a search to find the string order graph or order component or order clique or order tree to find them, and they did not.

I would not suggest using it, for several reasons:

• The phrase "$n$-order graph" looks like it might also mean something else related to finding orderings of something related to the graph. For example, a false positive I found in West's textbook was a citation of D.R. Woodall's paper "Cyclic-order graphs and Zarankiewicz's crossing-number conjecture" and that is what "$n$-order" feels like.

• The words "order" and "size" are fairly established terminology for the number of vertices and the number of edges, but they're also bad terminology; the distinction is completely opaque to someone unfamiliar with the terms, because it's in no way guessable. Personally, I try to use them correctly when I have to, but also try to make it clear from context what they mean.

• The alternative "$n$-vertex graph" is both clearer and is commmonly used.

I also do not think that "graph on $25$ vertices with minimum degree $5$" is ambiguous upon reflection - "minimum degree $5$" cannot refer to a vertex, only to a graph. But maybe it is better to avoid it anyway, because "$25$-vertex graph with minimum degree $5$" is also clear, and does not take any thought to realize it is unambiguous.

---

Part of the issue is just that the word order is ungrammatical: just like "$25$-vertex graph" refers to a graph with $25$ vertices, "$25$-order graph" would refer to a graph with $25$ orders. The correct way to turn "of order $25$" into an adjective is to say "order-$25$ graph".

This is still not used in the textbooks I checked, and it feels somewhat less formal to me, but one can find papers referring to either "order-$n$ graphs" or "order $n$ graphs" (the hyphen varies).