Is $K_1$ bipartite?

Question

I'm thinking that it could be trivially bipartite since it only has one vertex and no edges but I am still a little bit unsure about it being trivially bipartite.

Answer 1

Depends on your definitions. (As pointed out in Matthew Daly's answer, $K_1$ should be bipartite, because it has no odd cycles, so it would otherwise be an awkward exception. But not all definitions will play nicely with this desired property.)

West's Introduction to Graph Theory says

1.1.10. Definition. A graph $G$ is bipartite if $V(G)$ is the union of two disjoint (possibly empty) independent sets called partite sets of $G$.

So under this definition, if $V(K_1) = \{v\}$, then we let $\{v\}$ be one partite set, and $\varnothing$ be the other; $K_1$ is bipartite.

Bondy and Murty write

A graph is bipartite if its vertex set can be partitioned into two subsets $X$ and $Y$ so that every edge has one end in $X$ and one end in $Y$

which still works just fine, setting $X = \{v\}$ and $Y = \varnothing$. They do not specifically point out that $X$ or $Y$ could be empty, but they do not rule it out either. (Elsewhere, Bondy and Murty talk about "nontrivial partitions" or "partitions into nonempty parts", which make it clear that a partition without this qualifier is allowed to have an empty part.)

They are in better shape than Diestel, who has

A graph $G = (V, E)$ is called $r$-partite if $V$ admits a partition into $r$ classes such that every edge has its ends in different classes

with an earlier qualification that the classes of a partition may not be empty. Since $K_1$ should be bipartite by any reasonable definition, Diestel is in the wrong here. (Diestel later claims that all graphs with no odd cycles are bipartite, with no mention of $K_1$ as a special exception.)

If we treat "bipartite" as synonymous with "$2$-colorable", then $K_1$ is happily bipartite, since any function on its vertex set is a $2$-coloring (and also a $1$-coloring).

Answer 2

My graph theory professor spent a while teaching on this, because it's a mess either way.

It probably should be trivially considered bipartite. Otherwise you have to put disclaimers in all of your theorems (like the fact that $K_1$ doesn't contain any odd cycles). But $\{\{v\},\emptyset\}$ is not a valid partition of the vertex set, since it contains the empty set as a member.