The Student Room Group

D1 - graphs with vertices of the same degree

A simple graph of n vertices has each vertex of the same degree, d. What are the possible values of d?

It could be zero?

It could be 1 if n were even but not 1 if n were odd?

It could be 2 for all n?

But how do you work out other values for d without trying to draw a picture?

Thanks
Original post by maggiehodgson
A simple graph of n vertices has each vertex of the same degree, d. What are the possible values of d?

It could be zero?

It could be 1 if n were even but not 1 if n were odd?

It could be 2 for all n?

But how do you work out other values for d without trying to draw a picture?

Thanks


If every vertex has order k (known as a regular graph), and the graph has n vertices, then you can draw a simple graph if

nk is even and n > k

otherwise not.

Note: In your other thread for a graph on 5 vertices, k cannot equal 1, nor can it equal 3.
Original post by ghostwalker
If every vertex has order k (known as a regular graph), and the graph has n vertices, then you can draw a simple graph if

nk is even and n > k

otherwise not.

Note: In your other thread for a graph on 5 vertices, k cannot equal 1, nor can it equal 3.


Super. Thank you very much.

Quick Reply

Latest