0
$\begingroup$

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?

  • 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