0
$\begingroup$

I've been struggling through this and created a bunch of options where 12 work such as alternating colour 1 and 2 around the edges and having colour 3 in the middle, but I have a suspicion that there is a possibility with more. Could anyone help me please? Thank you !

Image explaining restrictions:

enter image description here

Image of Problem:

enter image description here

Thanks Again :)

$\endgroup$
1
  • $\begingroup$ Keep in mind that the edges don't have to be straight lines! (At least not in graph theory in general; it's possible that there's a restriction to straight lines somewhere else in the problem you're given.) $\endgroup$ Commented Nov 13 at 21:58

2 Answers 2

Reset to default
3
$\begingroup$

For a 7 node 3 color graph there can be a maximum of 14 edges. The general formula for the two constructions I have found for the maximum number of edges in a 3 color planar graph is:

$$E(n)=\begin{cases} 3n-6 & \text{ if } n = 3k \: :k \in \mathbb{N}\\ 3n-7 & \text{ otherwise } \end{cases}$$

For 7 nodes the 3 color graph looks as follows:

7 node 3 color planar graph

Further explanation is given in the answer to a similar question: Minimum nodes in a 36 edged shape with non-crossing edges and coloured nodes, with no similarly coloured nodes touching

$\endgroup$
-1
$\begingroup$

The max is 12 just due to the limits of how many edges you can have with the 7 nodes, to try and add another edge you would be required to first remove one so therefore 12.

$\endgroup$
1
  • 1
    $\begingroup$ You might want to reconsider.... $\endgroup$ Commented Nov 14 at 8:36

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.