Question
Every Eulerian Bipartite graph contains even number of edges.True/False
My Approach
Every Eulerian Bipartite graph. I can extract given important points from this
- Every Vertex has even degree
- Number of vertex$=m+n,\text{where m and n are number of vertex in each paritite }$
Using Handshaking lemma ,
$2k*(m+n)=2*\text{Number of edges,for some constant k ,since degree of each vertex is even}$
from above too, i am unable to conclude that Eulerian Bipartite graph has even number of edges .
Where am i missing?
Please help
Best Answer
Hint: You're not really using that the graph is bipartite*. What does an Eulerian cycle look like in a bipartite graph?
*You're saying that each part in the bipartite graph consists of some number of vertices and that the sum of those two is equal to the total number of vertices in a graph. It might seem like you're using bipartiteness here, but the same is true even for non-bipartite graphs, as long as you partition the vertex set into two in any fashion regardless of how it respects the edges of the graph.