# What is the term for a graph on $n$ vertices with no edges?

What is the term for a graph comprised of $n$ pairwise disconnected vertices?

I could call these $1$-colorable graphs or something like that, but I would rather use standard terminology if it exists.

Also is there a notation to go along with the name? For example $C_n$ generally denotes cycle graphs.

-
In England, if they are on your face they are called spots. – Will Jagy Mar 4 '13 at 23:09
I think the answers to this question should be helpful. – Adrián Barquero Mar 4 '13 at 23:11
@AdriánBarquero I see, so there is no consistency in notation either. Thanks. – Alexander Gruber Mar 4 '13 at 23:21
Obviously $G = (V,\varnothing)$ would be some solution, you could also try "complement of clique $K_n$". – dtldarek Mar 4 '13 at 23:21
@dtldarek Yeah: I think I might go for $\overline{K_n}$. – Alexander Gruber Mar 4 '13 at 23:48

The standard terminology is to call it the empty graph. Let me quote from the text [Bollobas, Modern Graph Theory, p.3], where he calls it the "empty graph": As $E_n$ is rather close to the notation for the edge set of a graph, we frequently use $\overline{K}_n$ for the empty graph of order $n$, signifying that it is the complement of the complete graph. In general, for a graph $G=(V,E)$ the complement of $G$ is $\overline{G}=(V,V^{(2)}-E)$; thus, two vertices are adjacent in $\overline{G}$ if and only if they are not adjacent in G.''

-

According to Wikipedia:

If it is a graph with no edges and any number $n$ of vertices, it may be called the null graph on $n$ vertices. (There is no consistency at all in the literature.)

You didn’t ask about notation, as distinct from terminology, but if the context is simple graphs, I’d denote it by $\langle[n],\varnothing\rangle$ or, if a different vertex set was wanted, $\langle V,\varnothing\rangle$ for the appropriate $V$.

-
Ouch, I must have missed that. Thanks. – Alexander Gruber Mar 4 '13 at 23:20
@Alexander: It’s pretty well buried on the page. I found it only because I did a Google search on "graph with no edges". – Brian M. Scott Mar 4 '13 at 23:26
There is not a lot of consistency I agree. But the I think the usual convention is that the null graph has no vertices; a graph with no edges is empty. (There's a paper by Harary and Schwenk "Is the null graph a pointless concept?" which goes some way to establishing the notation.) I'd be wary about accepting wikipedia as an authority on notation. – Chris Godsil Mar 5 '13 at 3:05

In "Introduction to Graph Theory", Douglas B. West calls a graph with no edges a "trivial graph". If it has no edges and no vertices, it's a "null graph".

There is no standardized terminology in graph theory. For this reason, many authors spend a few extra words precisely defining the terminology they use.

-