a) For the graph (in link above), write out the set of nodes, the set of edges, and the degree of each node. [6 marks]

I have attempted this question, however wanting to find out if it is correct what I have wrote and the formatting for the answer.

a) Set of nodes: A, B, C, D

Set of edges: e1, e2, e3, e4, e5

Degree of each node: Deg (A) = 2, Deg (B) = 3, Deg (C) = 3, Deg (D) = 2

b) What is the definiton of a path through a graph? Write out three paths through the graph above from A to B.

An alternating sequence of nodes and edges.

Now it says write out three paths through the graph A to B, so this what I wrote, is this three paths can someone confirm.

(A, {A,C}, C, {C,D}, D, {D,B}, B)

Thanks your help is much appreciated.

  • $\begingroup$ Seems right to me. Personally I define a path to be a sequence of nodes such that there exist edges between them, thus reducing the notation from $A \rightarrow \{A,C\} \rightarrow C$ to just $A \rightarrow C$. $\endgroup$ – A.E Aug 15 '13 at 16:01
  • $\begingroup$ Also I think they want three distinct paths starting at $A$ and ending at $B$, unless I am misinterpreting the question. $\endgroup$ – A.E Aug 15 '13 at 16:03
  • $\begingroup$ Yeah i see what you mean, but I think thats the way the teacher would like me to have it set out you see, thanks $\endgroup$ – Jay Aug 15 '13 at 16:04
  • $\begingroup$ That is what i was confused about to be honest, didn't know if it wanted three distinct paths, or for it to go through three paths before is gets to B $\endgroup$ – Jay Aug 15 '13 at 16:05
  • $\begingroup$ I think you might be right, I think I have to write 2 other paths, as I have only written one $\endgroup$ – Jay Aug 15 '13 at 16:09

You’ve correctly identified the nodes and edges, but there’s a small notational problem: the set of nodes is $\{A,B,C,D\}$, not $A,B,C,D$, and the set of edges is $\{e_1,e_2,e_3,e_4,e_5\}$, not just the list $e_1$, $e_2,e_3,e_4,e_5$. Your degrees are correct.

There are at least two slightly different definitions of path; you’ve given the more general one. Some authors require that no vertex be repeated; others call such a path a simple path. You’ve written down just one path from $A$ to $B$; you could write it more economically as $(A,e_4,C,e_3,D,e_5,B)$, but what you’ve written is also correct. You still need to find two more paths from $A$ to $B$, however. There are even two more simple paths from $A$ to $B$, one with one edge, and one with two edges.

  • $\begingroup$ Thanks, so I have to write 2 other paths, that is what i was confused about, I thought it meant write down one but make sure it goes through 3 paths before it gets to B. I understand now, will do that now. $\endgroup$ – Jay Aug 15 '13 at 16:08
  • $\begingroup$ The way I have set it out is the way the teacher showed me for the second part, even though it can be written more economically but he hasn't shown us that yet this year $\endgroup$ – Jay Aug 15 '13 at 16:08
  • 1
    $\begingroup$ @Jay: You’re welcome. In your original interpretation you were reading paths and thinking edges; you want to be sure to keep the two concepts straight. $\endgroup$ – Brian M. Scott Aug 15 '13 at 16:10
  • $\begingroup$ yeah thank you very much, that is exactly what I was thinking makes sense now $\endgroup$ – Jay Aug 15 '13 at 16:13

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.