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.


2 Answers 2



$$\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}$$

  • $\begingroup$ i'm sorry I'm not familiar with this structure $\endgroup$ Dec 1, 2013 at 0:54
  • 1
    $\begingroup$ @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$. $\endgroup$ Dec 1, 2013 at 1:09
  • $\begingroup$ Wow! How did you come up with this matrix? I have a similar problem that involves 10 vertices with different criteria. $\endgroup$ Dec 1, 2013 at 1:58
  • $\begingroup$ @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. $\endgroup$ Dec 1, 2013 at 2:08

Surely the graph is simple 3-connected, so start with that.

Two vertices in the middle will have degree 4.

This ends the exercise. (You should have a graph that has four half-triangles and two squares as spaces.

It won't be Eulerian, though, because it has vertices of odd degree. Hope this helps.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .