0
$\begingroup$

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?

$\endgroup$

1 Answer 1

0
$\begingroup$
  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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.