# Minimum and Maximum number of edges of a graph with vertex degree restricted

Today we were given this problem: Given a simple and connected graph with 7 vertices, such that they all have degree more than or equal to 2 and that at least two of them have degree less than or equal to 3, calculate the minimum and maximum number of edges of the graph. A bonus question was to determine the number of edges for which the graph could not be bipartite. What I thought: The minimum number of edges will be achieved when all vertices have degree $$2$$, so the number of edges will be $$7$$. I do not know how to justify the maximum, but I thought that I could have three vertices with degree $$6$$, two of them with degree $$4$$ and two of them with degree $$3$$, achieving $$16$$ edges. I know that a bipartite graph has at most $$n^2/4$$ edges ($$n$$ is the number of vertices of the graph), so edges must lie between $$7$$ and $$11$$. Moreover, the only graph with $$7$$ edges that fits the conditions is the 7-cycle, which is not bipartite, so we can restrict it to $$8-11$$. Any help/advice?

1. Apparently, we still need to prove that there cannot be $$17$$ edges or more under the given conditions. In fact, if our graph has at least $$17$$ edges, then removal of two vertices of degree $$3$$ will lead to removal of no more than $$6$$ edges. But then we would get a graph with $$5$$ vertices and at least $$11$$ edges, which is impossible.
2. Graph $$K_{3,4}$$ has $$12$$ edges and $$4$$ vertices of degree $$3$$. If a graph has $$7$$ vertices and $$13$$ edges, then it cannot be bipartite. This can be easily checked because graphs $$K_{1,6}$$ and $$K_{2,5}$$ have $$6$$ and $$10$$ edges respectively and it is obvious that any bipartite graph is complemented to a complete bipartite graph with the same number of vertices.