Minimum number of edges for a specific type of graph.

60 Views Asked by At

Let $G$ be a graph on $n \ge 6$ vertices.

What is the minimum number of edges required if we assume that the graph is both bipartite and Eulerian?

Also, can we characterize all such graphs as having a minimum number of edges?


We know that for the Eulerian graph we need all vertices to be of even degree. And due to bipartitedness we cant have odd cycles. Also, minimum edges are possible if we have partitions of equal size almost.

So even cycle will be one such graph. But I feel there will be more, like if $n$ is odd then?

1

There are 1 best solutions below

0
On BEST ANSWER

You're correct that, if $n$ is even, then the best you can do is a single cycle of length $n$.

For $n=2k-1$ odd, you clearly need at least $n$ edges, since the smallest Eulerian graph on $n$ vertices is an $n$-cycle. If there are $n+1$ edges, one vertex is of degree $4$ and the other $n-1$ are of degree $2$. You can show that such a graph must (if it is to be Eulerian) consist of two cycles joined at a vertex (which is common to both cycles). When $n\geq 7$, at least, you can make both of these cycles have an even number of vertices, and so this graph can be made bipartite. (For $n=5$ there are a few more annoying cases, while for $n=3$ no graph will work.)