2
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ Ummm... what is "k sub 1"? Do you instead mean $K_1$? $\endgroup$ – David G. Stork Jun 10 at 19:01
  • $\begingroup$ not only is it bipartite, it is also unipartite $\endgroup$ – Yorch Jun 10 at 19:02
  • $\begingroup$ @DavidG.Stork Yes, did not know how to make it like that in my title. Seemed to fix itself. $\endgroup$ – ThreeRingBinder Jun 10 at 20:23
1
$\begingroup$

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).

$\endgroup$
3
  • $\begingroup$ Quick question. Lets say we have 𝑋={𝑣} and 𝑌=∅, in reference to Bondy and Murty's definition. Would the edge connecting both subsets have vertices that are the empty set? Ie one empty set from X and the other from Y $\endgroup$ – ThreeRingBinder Jun 11 at 4:36
  • $\begingroup$ The definition says every edge has a certain property; it doesn't say there exist any such edges. Since $K_1$ has no edges, the definition holds. $\endgroup$ – Misha Lavrov Jun 11 at 5:24
  • $\begingroup$ Ah, makes sense now. Thanks! $\endgroup$ – ThreeRingBinder Jun 11 at 6:51
0
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ A reasonable definition of "bipartite" does not run into trouble if one partite set is empty. $\endgroup$ – Misha Lavrov Jun 10 at 19:24
  • $\begingroup$ @MishaLavrov On the other hand, requiring the parts of a partition to be non-empty isn't entirely unheard of either. So defining bipartite as a partition of the set of vertices into two can run into issues with $K_1$. $\endgroup$ – Arthur Jun 10 at 19:33
  • $\begingroup$ Yeah, I think that Dr. Schäffer's solution was to have us write in the margin of Bondy and Murty "... or $K_1$". $\endgroup$ – Matthew Daly Jun 10 at 19:44
  • $\begingroup$ But Bondy and Murty are totally fine with empty parts in a partition, as far as I can tell... $\endgroup$ – Misha Lavrov Jun 10 at 20:22
  • $\begingroup$ @MishaLavrov As I say, my professor assumed that "partitioned into two subsets $X$ and $Y$" means that $\{X,Y\}$ was a partition of the vertex set, which could not be legally done if one of the sets was empty. Bondy and Murty clearly either thought that it was okay or they hadn't considered the edge case, but pedantry like that got under my professor's skin. ^_^ $\endgroup$ – Matthew Daly Jun 10 at 20:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.