1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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’. :) $\endgroup$ – Haskell Curry Jan 15 '13 at 10:41
  • 1
    $\begingroup$ 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. $\endgroup$ – Martin Jan 15 '13 at 10:51
  • $\begingroup$ @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;) $\endgroup$ – Le Chifre Jan 15 '13 at 10:57
  • $\begingroup$ The maximum node degree is 4 not 8! $\endgroup$ – Jernej Feb 28 '13 at 8:41
  • 1
    $\begingroup$ 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? $\endgroup$ – Jernej Mar 4 '13 at 8:44
2
$\begingroup$

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