A graph $G$ has the property that every edge of $G$ joins an odd vertex with an even vertex. Show that $G$ is bipartite and has even size.

Some definitions:

  • A vertex of even degree is called an even vertex, while a vertex of odd degree is an odd vertex.

  • A graph $G$ is a bipartite graph if $V(G)$ (the set of vertices of $G$) can be partitioned into two subsets $U$ and $W$, such that every edge of $G$ joins a vertex of $U$ and a vertex of $W$.

  • Here size refers to the length of the graph, that is, to the number of edges.

What I've tried to do:

So, I've partitioned the set $V(G)$ into two subsets $E$ and $O$, where $E$ consists of the even vertices of $G$ and $O$ consists of the odd vertices of $G$.

By the property that the graph $G$ satisfies it follows that $G$ is bipartite? Do I have to show something else? I'm in doubt because it seems very easy.

Now for the second part of the exercise (G has even size) I know that if $H$ is a bipartite graph of size $m$ with partite sets $U=\{u_1,u_2,\ldots,u_s\}$ and $W=\{w_1,w_2,\ldots, w_t\}$. Since every edge of $H$ joins a vertex of $U$ and a vertex of $W$, it follows that adding the degrees of the vertices in $U$ (or in $W$) gives the number of edges in $H$, that is, $$ \sum_{i=1}^s \mbox{deg}(u_i) = \sum_{j=1}^t \mbox{deg}(w_j)=m, $$ where $\mbox{deg}(u)$ is the degree of a vertex $u$ in $H$.

Since $\mbox{deg}(u_i)$ is even for all $i=1,\ldots,s$ it follows that $$ \sum_{i=1}^s \mbox{deg}(u_i) = m $$ is even. Am I right? I'm confused because it seems to me that any bipartite graph has even size.

  • $\begingroup$ Why does it seem to you that any bipartite graph has even size? What about the bipartite graphs $K_2$, $K_{1,3}$, $P_4$, $P_6$, $K_{3,3}$, etc. etc. etc.? $\endgroup$ – bof Oct 6 '18 at 22:01
  • $\begingroup$ Oh thanks, I get it now. It would take a long time to explain my confusion here. But I was kind of messing around with a result that says every graph has an even number of odd vertices. Anyway, is my proof correct? $\endgroup$ – Ali Khan Oct 6 '18 at 22:51
  • $\begingroup$ I'm not seeing how the latter lets you conclude that the graph has even size. The numer $m$ is supposed to be the amount of vertices, not edges, right? $\endgroup$ – Guido A. Oct 6 '18 at 23:01
  • $\begingroup$ Your proof looks fine to me. $\endgroup$ – bof Oct 6 '18 at 23:20
  • $\begingroup$ @GuidoA. $m$ is the number of edges. $\endgroup$ – Ali Khan Oct 7 '18 at 0:01

Proof: Since every edge in $G$ joins an odd vertex with an even vertex, it cannot be the case that two odd/even vertices are adjacent. Hence, $G$ is an $X,Y$-bigraph such that $X$ is the set of even vertices, and $Y$ is the set of odd vertices.

We wish to show that $|E(G)|$ is even. Suppose, on the contrary, that $|E(G)|$ is odd. Thus, there are an odd number of edges that are incident to vertices in $X$. This is a contradiction, as each vertex in $X$ is even.

Therefore, if $G$ is a graph such that every edge connects an even and odd vertex, then $G$ is bipartite, and $|E(G)|$ is even.

  • 2
    $\begingroup$ I think we wish to show that the number of edges is even, not the number of vertices, though I am not 100% confident here. $\endgroup$ – Misha Lavrov Oct 7 '18 at 0:14
  • $\begingroup$ @MishaLavrov, thank you for the comment. The proof I had posted was flawed regardless. Ex. $K_{1,2}$ has odd $n(G)$ but satisfies the assumption. $|E(G)|$ being even is a more logical result. $\endgroup$ – Steve Schroeder Oct 7 '18 at 1:19

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.