0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Are you allowing multiple edges between two vertices? $\endgroup$ – Alex Feb 26 at 3:30
  • 1
    $\begingroup$ 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). $\endgroup$ – Math1000 Feb 26 at 3:31
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you so much. Your answer was very clear! $\endgroup$ – Mathstudent Feb 26 at 3:46

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.