# Notation for a graph without any edges?

Is there a standard notation for a graph (on a given set of vertices) without any edges?

• I'd call it a discrete set, or a discrete space, or a graph without edges. – Ryan Budney Aug 26 '10 at 4:02
• Looking at the answers, I conclude that there is no standard notation. E_n is as close as one gets, but it's too "verbal" for my taste. – Yuval Filmus Aug 27 '10 at 4:54

There are many ways to define a graph, but a pretty standard one is a pair $(V,E)$ where $V$ is a finite set of points and $E \subset \binom{V}{2}$. So, what you are looking for is $(V, \emptyset)$; which would be pretty widely understood.

• should that be $E \in V \times V$ ? – sleepless in beantown Aug 26 '10 at 14:55
• For directed graphs, $E \subset V \times V$. By graph, I mean a finite simple undirected graph (no loops or multiple edges), although the finiteness condition is not necessary. – Tony Huynh Aug 26 '10 at 15:21
• Sorry, I'm just not familiar with using the "choose" or "binomial" operator to literally mean "choose" in that way. For an undirected graph, wouldn't an edge consist of an element of the set defined by {$V_1, V_2$} such that $V_1 \in V$ and $V_2 \in V$? I just want to make sure that I understand the notation correctly, because I did not realize that $A \times B$ for sets $A$ and $B$ implied an ordered pair $(a_1, b_1) s.t. a_1 \in A, b_1 \in B$. Thanks for the clarification. – sleepless in beantown Aug 27 '10 at 6:53
• And for simple graphs with no loops, $V_1 \ne V_2$ – sleepless in beantown Aug 27 '10 at 6:55
• Yes, for an undirected graph an edge is just an unordered pair of vertices. So the notation $\binom{V}{2}$ simply means the collection of all 2-element subsets of $V$. It's not completely standard, but I like it. – Tony Huynh Aug 27 '10 at 9:13

Some people call it the empty graph on n vertices.

• That's also what I call it, but I want some notation, like the ones they have for the empty string. – Yuval Filmus Aug 27 '10 at 4:52

I don't think there is standard notation for this. If you've already fixed a notation for complement (say a superscript c) then you could use $K_n^c$. But I don't think standard notation exists for this.

I have seen $\bar{K}_n$ for the graph with n vertices and no edges, but I do not remember where.

I suppose $n\cdot K_1$ assuming of course that $n \ge 1$. In the event that there are also no vertices it is sometimes called the Null Graph although F. Harary, F. and R. Read in "Is the Null Graph a Pointless Concept?" suggest that it may be more trouble than it is worth in that it has too many edges to be a tree, no automorphism group etc.

• Huh? The totally empty graph definitely is not a tree, as it has too many edges, but the automorphism group is trivial, not nonexistent. There's one way to do nothing to nothing. – Theo Johnson-Freyd Aug 26 '10 at 5:49
• Well, let me qualify that. One nice way to count automorphisms is whenever you have a disjoint union of isomorphic things, and each component has automorphism group $G$, then you expect the union to have automorphisms the wreath product $G \wr S_n$. But this is a wrong expectation: it undercounts, for example, when $G$ is itself a disjoint union. So it's not surprising that it overcounts here. The totally empty graph has zero components, and is not itself connected. – Theo Johnson-Freyd Aug 26 '10 at 5:52
• Mainly I just couldn't pass up an opportunity to work in the title of that article. – Aaron Meyerowitz Aug 26 '10 at 6:11
• Hm. I would define a tree to be a connected graph lacking cycles; the null graph certainly qualifies, although the connected part is more vacuous than the absence of cycles. Equivalently, between any two distinct vertices you may care to choose in the null graph, there is exactly one path between them. – Niel de Beaudrap Aug 26 '10 at 11:41
• Actually, as Theo says there is good reason to consider the null graph as not connected. To see why, check out the article above by Harary and Read; it's quite funny. – Tony Huynh Aug 26 '10 at 11:56

I have seen it written as $E_n$, where E stands for empty.

Standard notation in graph theory? In category theory the analogous thing can be denoted $disc(V)$ where $V$ is the set of vertices.