# Graph Theory Question involving: Nodes, edges, degrees and paths 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.

• 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$. – A.E Aug 15 '13 at 16:01
• Also I think they want three distinct paths starting at $A$ and ending at $B$, unless I am misinterpreting the question. – A.E Aug 15 '13 at 16:03
• 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 – Jay Aug 15 '13 at 16:04
• 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 – Jay Aug 15 '13 at 16:05
• I think you might be right, I think I have to write 2 other paths, as I have only written one – 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.