1
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ i'm sorry I'm not familiar with this structure $\endgroup$ – user2510809 Dec 1 '13 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$ – Brian M. Scott Dec 1 '13 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$ – user2510809 Dec 1 '13 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$ – Brian M. Scott Dec 1 '13 at 2:08
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.