Are "unlabeled" graphs isomorphism classes of labeled graphs? How can people say things like $K_n$ is "the" complete graph on $n$ vertices?

Question

For example when one says something along the lines of $K_n$ is the complete graph on $n$-vertices what exactly are they referring to? An unlabeled graph or a labeled graph?

If its labeled then don't they have to specify $E(K_n)$ and $V(K_n)$ first?

If its unlabeled then is it an isomorphism class? If not then what it is formally?

Are unlabeled graphs not isomorphism classes of labeled graphs?

Answer 1

The math is more important than the formal description of the math.

Yes, if we're defining a (simple) graph as a pair $(V,E)$, where each $e \in E$ is a subset of $V$ of size $2$, then there are multiple graphs that are "complete graphs on $n$ vertices". So we could let $K_n$ denote the isomorphism class of complete graphs on $n$ vertices, and sometimes we refer to such an isomorphism class as an "unlabeled graph".

But in practice, it's convenient to make statements like "The complete graph on $n$ vertices has $\binom n2$ edges", and pretty much everyone does it when the vertex set is irrelevant, which is almost always. It would be more technically correct to say "Every complete graph on $n$ vertices has $\binom n2$ edges", but this statement is a bit confusing. It reminds us of the statement "Every tree on $n$ vertices has $n-1$ edges", but unlike the statement about trees, the statement about complete graphs doesn't actually need to consider multiple different cases. Once you've proven that one complete graph on $n$ vertices has $\binom n2$ edges, you know that they all do.

In actual usage, it makes the most sense to interpret $K_n$ as denoting an arbitrary complete graph, whose vertex set we don't care about, because everything we say will work no matter what it is.

P.S. I'd be careful about the word "labeled graph". This, in actual usage, can be understood to mean something like "graph with vertex set $\{1, 2, \dots, n\}$ for some $n$". For example:

• When we ask "How many unlabeled trees are there on $n$ vertices?" it's fair to translate that into "How many isomorphism classes of trees with $n$ vertices are there?"
• When we ask "How many labeled trees are there on $n$ vertices?" the answer is $n^{n-2}$, not $\infty$: we are asking about the number of trees on a fixed set of $n$ vertices, which doesn't need to be $\{1,2,\dots,n\}$ but might as well be.

Answer 2

When people talk about $K_n$ they are talking about unlabeled graphs. Unlabeled graphs are much more common than labeled graphs, and if no qualifier is given, it's all but certain that an unlabeled graph is meant. Yes, it's (a representative of) an isomorphism class.

I don't quite understand the meaning of the last question. Unlabeled graphs are not labeled graphs, clearly, so how could they be isomorphism classes of labeled graphs? Also, a graph is not an isomorphism class, but a representative of such a class.