# Drawing a simple connected graph with certain criteria

Draw a simple graph G with 8 vertices that satisfy all of the conditions listed below:

1. each vertex has a degree of at least 3

2. the graph is not regular meaning not all vertices have same degree

3. the graph contains a hamiltonian and Eulerian circuit.

I have been sitting here drawing out graphs to match these criteria but I can't figure it out. I know that all the vertices have to have even degree for a Eulerian circuit to exist. any help/ Suggestions? I know there must be a method to this than just through trial and error by drawing.

HINT:

$$\begin{bmatrix} 0&1&1&0&1&1&1&1\\ 1&0&1&1&1&1&0&1\\ 1&1&0&1&1&0&0&0\\ 0&1&1&0&1&1&0&0\\ 1&1&1&1&0&1&1&0\\ 1&1&0&1&1&0&1&1\\ 1&0&0&0&1&1&0&1\\ 1&1&0&0&0&1&1&0 \end{bmatrix}$$

• i'm sorry I'm not familiar with this structure – user2510809 Dec 1 '13 at 0:54
• @user2510809: It’s the adjacency matrix of a graph. Label the vertices of the graph $1,2,\ldots,8$. There is a $1$ in row $r$, column $c$ if and only if the graph has an edge between $r$ and $c$. – Brian M. Scott Dec 1 '13 at 1:09
• Wow! How did you come up with this matrix? I have a similar problem that involves 10 vertices with different criteria. – user2510809 Dec 1 '13 at 1:58
• @user2510809: I started with the cycle $1\to 2\to\ldots\to 8\to 1$, so as to have the Hamilton circuit. I know that to get the Euler circuit I need to make sure that every vertex has even degree, which in this case means that it has to be at least $4$, so I added the cycles $1\to 3\to 5\to 7\to 1$ and $2\to 4\to 6\to 8\to 2$. Then I just tinkered a bit to kill off regularity. – Brian M. Scott Dec 1 '13 at 2:08