Each vertex in graph $G$ is composed of a string of length $3$ from digits $\{0,1,2\}$. There's an edge between two vertices iff their respective strings have only one digit in common. For example, $012$ and $021$ have an edge because their first digit is the same while the other digits are different. What is the degree of each vertex?

I think that once we choose the digit which is the same there're $3^2$ possibilities to permute the digits in the other two places. But I'm not sure this is correct.

  • 3
    $\begingroup$ $012$ and $022$ have two digits in common $\endgroup$ – mathworker21 Jun 28 '18 at 7:41
  • 1
    $\begingroup$ and so for each digit there are $2^2$ possibilities for the other two non-matching digits of the vertices it is connected to $\endgroup$ – Henry Jun 28 '18 at 7:43
  • $\begingroup$ @mathworker21 thank you, I corrected the example $\endgroup$ – user123429842 Jun 28 '18 at 7:47

If we fix one places in a 3-digit string then there are $2 \times 2 = 4$ possibilities for the other two places that create strings with just one digit in common with the original string.

For example, fixing the first place in $012$, we see that $012$ is linked to $000$, $001$, $020$ and $021$. So that gives us 4 edges.

If we fix the second place we get a further 4 edges. And if we fix the third place we get 4 edges again, giving a total of 12 edges. We are not double counting any edges. So each vertex has degree 12.

| cite | improve this answer | |

There are a total of $27$ vertices in the graph. The number of string containing only $1$ and $2$ is $8$, hence there are $19$ vertices in which $3$ appears. Similarly for $1$ and $2$.

For the vertices we have the following:

$3$ contain a single digit

$18$ contain exactly $2$ digits

$6$ contain all $3$ digits

Using the information above we have:

The $3$ single digit vertices are of degree $19-1=18$

The $18$ vertices containing $2$ digits are of degree $26-1=25$

The $6$ remaining vertices are of degree $26$

| cite | improve this answer | |
  • $\begingroup$ All of the vertices have the same degree. I wonder if the OP is confusing you. $\endgroup$ – user123429842 Jun 28 '18 at 10:49
  • $\begingroup$ How do all vertices have the same degree??? $\{1,1,1\}$ and $\{1,1,2\}$ for sure have different degrees (just an example) $\endgroup$ – asdf Jun 28 '18 at 11:06
  • $\begingroup$ @asdf The order of the digits matters. Using the example from the OP: $012$ and $021$ use the same digits $0$, $1$, and $2$, but they only have the first digit in common. $\endgroup$ – Bram28 Jun 28 '18 at 14:20

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.