0
$\begingroup$

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?)

  • 0
    @Graphth: I interpret ing to be asking what the maximum possible number of vertices is.2012-10-20

2 Answers 2

3

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)$.

  • 0
    @ing: Yes: you have $34\ge 4n$, so $n\le\frac{34}4$, and since $n$ must be an integer, $n\le 8$.2012-10-20
0

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 <span class=24 non-isomorphic $8$-vertex $17$-edge connected graphs with minimum degree $\geq 4$.">

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.