0
$\begingroup$

find the number of way that we can coloring the vertices of the following graph with 3 colors : red,white and green such that no two adjacent vertices are of the same color; this is called a vertex coloring.

enter image description here

i think we have $3!$ ways for right above triangle and $2 \times 2$ ways for left above triangle so answer is $3! \times 2 \times 2 =24$ .is this true ?

$\endgroup$
3
  • $\begingroup$ As you said and as commented by Morgan, among the $2 \times 2$ ways of coloring the left triangles, in one case you can choose the color of the middle vertex, therefore, the number of possible colorings is $30$. $\endgroup$
    – Vezen BU
    Commented Jan 4, 2023 at 8:01
  • $\begingroup$ @VezenBU: That looks like an answer to me, not a comment. $\endgroup$
    – joriki
    Commented Jan 4, 2023 at 10:23
  • $\begingroup$ Can the graph rotate in 3D or 2D ,because we may need to apply Burnsides' lemma in that situations $\endgroup$ Commented Jan 4, 2023 at 16:13

1 Answer 1

1
$\begingroup$

As you said and as commented by Morgan, among the $2 \times 2$ ways of coloring the left triangles, in one case you can choose the color of the middle vertex, therefore, the number of possible colorings is $30$ instead of $24$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .