Let G be the undirected graph given below Find the number of

Let G be the undirected graph given below. Find the number of paths from vertex a to vertex b. Find the number of trails from vertex a to vertex b. Find all cycles starting at vertex a. Determine number of vertices, edges, and regions and show that your answers satisfy Euler\'s Theorem for connected planar graphs. Find a dual graph.

Solution

a)The paths from a to b are

ab, adb,adcb - 3 paths.

b)The trails from a to b are

ab, adb,adcb - 3 trails.

c)Cycles starting at a vertex a

abda, abcda - 2 cycles

d) Number of vertices - 8, Number od edges - 11, Number of regions -5

Eulers Theorem - Let X = (V, E) be a connected planar graph. Then the number of faces, denoted Nf , in any planar embedding of X satisfies |V | |E| + Nf = 2

Number of internal faces= 4, Number of external faces= 1, total number of faces =5

then by Eulers theorem Nf= 2-(8-11)= 5 , is true