# What is vertex degree if each vertex represents a string of $\{0,1,2\}$ and there's edge between vertices iff the strings have one digit in common?

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.

• $012$ and $022$ have two digits in common – mathworker21 Jun 28 '18 at 7:41
• and so for each digit there are $2^2$ possibilities for the other two non-matching digits of the vertices it is connected to – Henry Jun 28 '18 at 7:43
• @mathworker21 thank you, I corrected the example – 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.

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$

• All of the vertices have the same degree. I wonder if the OP is confusing you. – user123429842 Jun 28 '18 at 10:49
• How do all vertices have the same degree??? $\{1,1,1\}$ and $\{1,1,2\}$ for sure have different degrees (just an example) – asdf Jun 28 '18 at 11:06
• @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. – Bram28 Jun 28 '18 at 14:20