# Let $G=(V,E)$ be a connected graph with $|E|=17$ and for all vertices $\deg(v)>3$. What is the maximum value of $|V|$?

Let $G=(V,E)$ be a connected graph with $|E|=17$ and for all vertices $\deg(v)>3$. What is the maximum value of $|V|$? (What is the maximum possible number of vertices?)

-
What is max v?? – Graphth Oct 20 '12 at 13:23
@Graphth: I interpret ing to be asking what the maximum possible number of vertices is. – Brian M. Scott Oct 20 '12 at 13:26

HINT: Suppose that $V=\{v_1,\dots,v_n\}$. Then $$\sum_{k=1}^n\deg(v_k)=34\;;\tag{1}$$ why?

If $\deg(v_k)\ge 4$ for $k=1,\dots,n$, then $$\sum_{k=1}^n\deg(v_k)\ge\sum_{k=1}^n4\;.\tag{2}$$ Now combine $(1)$ and $(2)$.

-
maximum possible number of vertices is = 8? – geni Oct 20 '12 at 14:02
@ing: Yes: you have $34\ge 4n$, so $n\le\frac{34}4$, and since $n$ must be an integer, $n\le 8$. – Brian M. Scott Oct 20 '12 at 14:03

There are $24$ non-isomorphic $8$-vertex $17$-edge connected graphs with minimum degree $\geq 4$. They can be generated using geng which comes with nauty using the command:

geng 8 17:17 -d4 -c


I wrote a script to display the output. Here's the result:

The first one is $K_{4,4}$ with an additional edge.

By the way, if we attempt

geng 9 17:17 -d4 -c


we receive the response:

>E geng: impossible mine,maxe,mindeg,maxdeg values


which gives a computer verification that $8$ is indeed the maximum value.

-