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?)
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|$?
0
$\begingroup$
graph-theory
-
0@Graphth: I interpret ing to be asking what the maximum possible number of vertices is. – 2012-10-20
2 Answers
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:
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.