Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am currently work on a problem about these two graphs I mentioned in the title:

enter image description here

  • The maximum node degree is: $8$ because there are 8 nodes
  • The graph has subgraphs: $8$ because of the 8 nodes(every node could be a subgraph)
  • Is the graph an Eulerian graph: $YES$
  • Is the graph an hamiltonian graph: $NO$
  • Is this graph an acyclic graph: $NO$ because there are cycles in this graph
  • Does the graph contains a spanning subtree:$YES$ because when you connect every outer border with a node you get a spanning subtree

Are my argumentations correct?

share|cite|improve this question
You will have to translate some of the German adjectives to English. For example, ‘eulerscher’ should be ‘Eulerian’ and ‘hamiltonischer’ should be ‘Hamiltonian’. Also, I would like to see the definition of an ‘exciting tree’. :) – Haskell Curry Jan 15 '13 at 10:41
I think one of the two "eulerscher" in the third and fourth bullets should be "hamiltonischer", or are you undecided? :) It might help to see how you got those numbers for the maximum node degree, the number of subgraphs, etc. – Martin Jan 15 '13 at 10:51
@HaskellCurry yes you are right, its hard if you only have a german textbook to translate it into proper english... btw I updated my post;) – Le Chifre Jan 15 '13 at 10:57
The maximum node degree is 4 not 8! – Jernej Feb 28 '13 at 8:41
The degree of a node is the number of edges incident with the given node. Which vertex has the maximal number of incident edges to it and how many? – Jernej Mar 4 '13 at 8:44
up vote 2 down vote accepted

Your answers are not entirely correct. Few corrections and comments following:

  • Every graph (unless perhaps the empty graph) has subgraphs. Plenty of them. The graph on the picture has more than 8 subgraphs.
  • The graph is clearly Hamiltonian (can you find a 8-cycle in it?)
  • The graph indeed contains a spanning tree. In fact every connected graphs contains a spanning tree
share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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