I am working on a problem set for school right now and I have the following question:
Let $G$ be an arbitrary bipartite graph. What is the smallest possible girth of $G$? Explain
I have been thinking about this problem and I believe the answer is 2, because you could have a loop between two vertices $u,v$ where when $A$ and $B$ are bipartitions of a bipartite graph $G$ you have $u\in A$ and $v\in B$. I guess my question is: are loops possible in a bipartite graph? I think they are but we have spent so much time on simple graphs this semester I just want to make sure. Any help would be greatly appreciated.
If you allow multiple edges between vertices, then you could argue that the answer is 2 in the way you describe. However I suspect the question means to restrict you to simple graphs:
Let $G = (A, B)$ be a (simple) bipartite graph. Suppose its girth is 3. Then there is a cycle $u\to v\to w\to u$. Suppose WLOG that $u \in A$. Then we must have that $v \in B$, $w \in A$. But $u$ is adjacent to $w$, which contradicts that $G$ is bipartite. (recall that a bipartite graph can have no odd cycle). Then the girth of $G$ is at least 4. Since there exists a bipartite graph with girth 4 (say $K_{2,2}$), and none with girth $\leq 3$, the smallest possible girth of $G$ is 4.