0
$\begingroup$

What is the minimum degree of a four-regular graph of diameter 2.

From trial and error I have concluded that the minimum degree is six. Explanation: If I start from one node then there must be 4 edges off this and each one of these edges must have a node attached to it, this gives us 5 nodes. Since the graph has diameter 2 I have to add a sith node to achieve this. Connecting these nodes with various edges will result in them all having degree four.

How would one rigorously justify this though?

$\endgroup$
0
$\begingroup$

Your argument is fine to show that the degree must be at least six. If you draw a graph the way you describe, you can show that you can meet the requirement with a graph of degree six, so you are done. It is $K_6$ with three edges deleted. The three edges connect disjoint pairs of vertices. It is also the skeleton of the octahedron.

$\endgroup$

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.