Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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

2 Answers 2

up vote 3 down vote accepted

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

share|improve this answer
    
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 $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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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