Maximum cut vertices of an Eulerian graph

Question

How can I find maximum number of cut vertices of a Eulerian graph with $n$ vertices?

Answer 1

I have found that the formula for maximum possible number of vertices in an eulerian graph is $\lfloor\frac{n-3}{2}\rfloor$.

In order to prove it you should us strong induction to prove that the maximum is $\lfloor\frac{n-3k}{2}\rfloor$ which can be done by choosing one of the cut vertices (v) and replacing it with s + 1 other vertices which are the number of subgraphs formed by removing v and replacing each edge of v with one of the new vertices and the corresponding vertex.
Finally we would have n + s vertices and k + s sub graphs. Based on inductions assumption the maximum number of vertices is $\lfloor\frac{n+s-3k-3s}{2}\rfloor + 1$.

Answer 2

First observe that every connected graph contains at least two vertices that are not cut vertices (consider a maximal path, its end-vertices cannot be cut vertices).

So if an Eulerian graph has $n$ vertices, it certainly cannot contain more than $n-2$ cut vertices.

If your Eulerian graph is not simple, then there is a nice construction that shows this number $n-2$ is attainable. Hint: it looks a bit like a path.