Can a $k$-regular graph with $99$ vertices $(G=(99,E))$ be a bipartite graph?

35 Views Asked by At

I was reviewing some exams from previous years on Graph Theory and I'm stuck on this question.

What I have so far is that for a graph to be bipartite, we need to have $2$ subsets of $V=99$

$(G=(V,E) \Rightarrow G=(X \cup Y, E))$, where:

$|V(X)|+|V(Y)|=|V(G)|=99$

$|V(X)|\cdot|V(Y)|=|E|$

$|E|=\dfrac{k|V(G)|}{2}$

Do I just solve these equations for k or am I completely off and need to prove this some other way?

1

There are 1 best solutions below

3
On

Hint Show that in a regular bipartite graph you have $$|E|=|V(X)|*k=|V(Y)|*k$$