Alan Tucker's Applied Combinatorics state, "A set of eight binary digits (0 or 1) are equally spaced about the edge of a disk. We want to choose the digits so that they form a circular sequence in which every subsequence of length three is different. Model this problem with a graph with four vertices, one for each different subsequence of two binary digits. Make a directed edge for each subsequence of three digits whose origin is the vertex with the first two digits of the edge’s subsequence and whose terminus is the vertex with the last two digits of the edge’s subsequence."
I have to a) build this graph b) Show how an Euler cycle (which exists for this graph) will correspond to the desired 8-digit circular sequence. c)Find such an 8-digit circular sequence with this graph model.
I'm not sure how to build the graph, more explicitly, should the vertex essentially have a coordinate with binary numbers? Such as, (1,0) (0,1), (1,1), (0,0) and would these be in a circle, or some type of cycle?
Anything to get me started please!
This is very pretty.
Hints to get you started:
You have found the four vertices of your graph. Each is a subsequence of two digits
Each vertex will have two directed edges leaving it, pointing at vertices whose first digits match its last digit
For example $(0,1)$ ends with $1$ so will have edges pointing at $(1,0)$ and $(1,1)$, both of which start with $1$
Each edge is in effect a triplet. For example the edge from $(0,1)$ to $(1,1)$ is the triplet $(0,1,1)$ taking account of the overlap
There are $4 \times 2=8$ edges in total corresponding to the $2^3=8$ different subsequences of three digits
So a Eulerian cycle (there are in fact two) using each edge once will give you what you want
Not that the question asks you to do so, but you can make the triplets vertices with directed quadruplet edges and look for a Hamilonian cycle