# Why isn't this graph bipartite?

This is a very silly question but I can't seem to figure it out.

Let $$G$$ be the graph with 6 nodes and 3 edges where 1 is connected to 4, 2 to 5 and 3 to 6. Le $$U = \{1,2,3\}$$ and $$V=\{4,5,6\}$$. Then each edge connects one node in $$U$$ with one node in $$V$$. It's adjacency matrix is:

$$\begin{pmatrix} 0 & 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 0 & 0 & 1\\ 1 & 0 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 & 0\\ \end{pmatrix}$$

Which to me looks like a bipartite adjacency matrix but of course $$A^2 = Id$$ so $$A^k = Id$$ for all $$k \geq 2$$ which contradicts that $$A^{2n+1}$$ has 0s in the diagonal for all n if A is the adjacency matrix of a bipartite graph.

Any help is greatly appreciated, I seem to be missing a very basic thing.

• How did you get that $A^k=Id$ for all $k\ge2$? That's not the case.
– Karl
Nov 16, 2021 at 3:31

By $$A^2=I,$$ you won't have $$A^k=I,$$ instead you have $$A^{2n}=I,$$ $$A^{2n+1}=A.$$ This won't contradict the proposition about bipartite graph.

• Of course you're right. Not sure how I convinced myself of that! Thanks a ton! Nov 16, 2021 at 12:32 Check the definition of a bipartite graph.

A definition for bipartite is:

A graph is bipartite if the vertices can be divided into two groups and all egdes are between the groups.

So You have two groups already in Your question and the check is therefore trivial. And atop Your egdes are only between those two groups so there is not prove in need for the answer or confirmation.

Another problem is that the given matrix is a reordering of the generic matrix representing your problem given the picture from Mr. Stork is accepted. This matrix fulfills the given requirements.

This stems rigorously from the representation of the graph on the paper and is a convention. Your problem is reenumerating 1->3, 2->4 and 3->5. The second row of the matrix is representing 3, the third is 2 and the fifth is 3.

This is not tedious work. It is not an error of Yours. It seems a missing accepted working definition of the adjacency matrix. I reference to Mathematica or Wolfram Alpha for such cases. The definition is a vertex - vertex matrix of the graph. Very simple, very abstract.