V is the set of those two-letter words built over {w, x, y, z} whose first letter is y or z. The graph G = (V, A) is defined so that two words of V determine an edge of A if they differ in exactly one point.
a) How many vertices does G? b) Draw the graph G.
I would like to know if my procedures are right?
a) First I find V = {(y,w),(y,x),(y,y),(y,z),(z,w),(z,x),(z,y),(z,z)}
I have calculate 16 edges, I don't know if this is right. Could you help me with that.
b) With my edges I draw a graph with 8 nodes, I can't draw here. Could you suggest me a place to draw a graph easily?
Thanks for your time
(a) You are correct.
For any word $W$ starting with some letter $l$, there are exactly three other words starting with $l$, and these all have a different letter in the second position. Also, for any word $W_1$ ending in $l$, there is only one other word $W_2$ that ends with $l$, and $W_1$ and $W_2$ are guaranteed to have a different letter in the first position. So for any word $W$, there are exactly four other words that differ from $W$ in one 'point'.
In the graph, then, every word will be incident to exactly four edges, meaning that every vertex has a degree ($\delta$) of 4. The sum of all vertex degrees is then equal to 4 times the number of vertices. Formally:
$$\sum_{v \in V(G)} \delta(v) = 4|V(G)| = 4 \cdot 8 = 32$$
The handshaking lemma states that the sum of all vertex degrees equals twice the number of edges. Formally:
$$\sum_{v \in V(G)} \delta(v) = 2|E(G)|$$
Substituting:
$$32 = 2|E(G)|$$ $$16 = |E(G)|$$
So the number of edges is indeed 16.
(b) This is off-topic, but you could try Gliffy or yED.