# Smallest possible girth of an arbitrary bipartite graph

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.

• Are you allowing multiple edges between two vertices? – Alex Feb 26 at 3:30
• By definition, a graph with a loop cannot be bipartite. If multiple edges between vertices are allowed, then there could be a cycle of length two. Otherwise, the smallest possible girth is four (since a bipartite graph cannot have odd cycles). – Math1000 Feb 26 at 3:31

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.