Does there exist a multigraph $G$ of order $8$ such that the minimal $d(G) = 0$ while maximal $d(G) = 7$? What if ‘multigraph $G$’ is replaced by ‘graph $G$’?

Answer: such multigraph does not exist, but graph?

  • $\begingroup$ 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. $\endgroup$ – J. M. is a poor mathematician Jul 27 '12 at 13:47
  • $\begingroup$ alright! thank you. I was writing graph theory with a space and not with a '-' $\endgroup$ – Intellectual_ Jul 27 '12 at 14:01
  • 1
    $\begingroup$ 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. $\endgroup$ – Luke Mathieson Jul 27 '12 at 14:24
  • $\begingroup$ Isn't every graph trivially a multigraph? $\endgroup$ – JeffE Jul 27 '12 at 15:49

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
    $\begingroup$ 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. $\endgroup$ – Legendre Jul 27 '12 at 14:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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