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 Answers 2

Reset to default
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$
4
  • $\begingroup$ i'm sorry I'm not familiar with this structure $\endgroup$
    – user2510809
    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$
    – Brian M. Scott
    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$
    – user2510809
    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$
    – Brian M. Scott
    Dec 1, 2013 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$

You must log in to answer this question.

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