What is the maximum value of $|V|$

253 Views Asked by At

If $G=(V,E)$ is a connected graph with $|E|=17$ and $deg(v)>2$ for all vertices of graph $G$, what is the maximum value for $|V|=v$?

$deg(v)\geq 3$ for all $v\in V$, $\sum_{v\in V} deg(v)=2|E|=2\cdot 17=34$, thus $34\geq 3v$ and from there $v \leq \frac{34}{3} \approx 11.33$, $v\leq 11$. $v_{\text{max}}=11$.

Those were my thoughts, but it wasn't enough, apparently I only gave an upper bound.

Am I missing something?

1

There are 1 best solutions below

4
On BEST ANSWER

I think your reasoning is correct and one can show that there exists a connected graph with $11$ vertices and $17$ edges:

enter image description here

Note that I constructed this graph by using your arguments actually, since degree sum was $34$ and $v_{max} = 11$, I consider $10$ vertices of degree $3$ and $1$ vertex with degree $4$. Easiest way to construct such a graph is to consider an $11$-cycle first, then first make a vertex with degree $4$ (this also makes two of the vertices degree $3$ so we are left with $8$ vertices of degree $2$), then try to pair vertices so that they all have degree $3$.