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.
Best Answer
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.