Tell me more ×
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.
up vote 0 down vote favorite

Question: Does there exist a multigraph G of order 8 such that Minimum d(G) = 0 while Maximum d(G) = 7? What if ‘multigraph G’ is replaced by ‘graph G’?

Answer: such multigraph does not exist, but graph?

share|improve this question
Since this is your second question on the matter, allow me to tell you a tiny tip: you will notice that as you type in tags for this question, there should be a short description on when you should use the tag. If you will read it, you'll then notice that it is graph-theory and not graph that you should be using as the tag. I will retag this for you for now, but please be more attentive the next time. – J. M. Jul 27 '12 at 13:47
alright! thank you. I was writing graph theory with a space and not with a '-' – Intellectual_ Jul 27 '12 at 14:01
1  
I'm not clear as to why a multigraph with these properties does not exist. As you can have multiple edges between a pair of vertices, pick two, put seven edges between them and add no other edges. Then the other 6 vertices have degree 0. – Luke Mathieson Jul 27 '12 at 14:24
Isn't every graph trivially a multigraph? – JeffE Jul 27 '12 at 15:49

1 Answer

up vote 3 down vote

If a graph, G, has order 8, it has 8 vertices. If maximum d(G) = 7, it has a vertex, v, of degree 7.

Then, vertex v is connected to 7 neighbors, each of which has degree at least 1 because they are at least connected to v. So, minimum d(G) must be at least 1.

So, there is no graph that fits your criteria.

share|improve this answer
1  
I am using the usual definition of "graph" in which self loops are not allowed. If self loops are allowed, each loop adds 2 to the degree. We can create your graph by letting vertex v have a self loop, as well as 5 other neighbors. Then, let the other 2 vertices that are not neighbors of v be isolated vertex. – Legendre Jul 27 '12 at 14:01

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.