  Connectedness and bipartiteness are basic properties of classical graphs, and
the purpose of this paper is to investigate the case of quantum graphs. We
introduce the notion of connectedness and bipartiteness of quantum graphs in
terms of graph homomorphisms. This paper shows that regular tracial quantum
graphs have the same algebraic characterization of connectedness and
bipartiteness as classical graphs. We also prove the equivalence between
bipartiteness and two-colorability of quantum graphs by comparing two notions
of graph homomorphisms respecting adjacency matrices or edge spaces. In
particular, all kinds of quantum two-colorability are mutually equivalent for
regular connected tracial quantum graphs.
