# Graph that joins an odd vertex with an even vertex

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.

• 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.? – bof Oct 6 '18 at 22:01
• 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? – Ali Khan Oct 6 '18 at 22:51
• 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? – Guido A. Oct 6 '18 at 23:01
• Your proof looks fine to me. – bof Oct 6 '18 at 23:20
• @GuidoA. $m$ is the number of edges. – 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.
• @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. – Steve Schroeder Oct 7 '18 at 1:19