0
$\begingroup$

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?

  • 0
    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 [tag:graph-theory] and not [tag: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.2012-07-27
  • 0
    alright! thank you. I was writing graph theory with a space and not with a '-'2012-07-27
  • 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.2012-07-27
  • 0
    Isn't every graph trivially a multigraph?2012-07-27

1 Answers 1

3

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.

  • 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.2012-07-27