Chapter 5, Problem 1E

For the graph shown in Fig 5-29,

a. give the vertex set.

b. give the edge list.

c. give the degree of each vertex.

d. draw a version of the graph without crossing points.

To determine

(a)

To find:

The vertex set of given graph.

Answer to Problem 1E

Solution:

The vertex set is $\left\{A,B,C,X,Y,Z\right\}$.

Explanation of Solution

In the graphical representation of routes, the location is defined as a dot in the graph. Those dots are the vertices of the graph and the collection of vertices come under the vertex set.

Given:

The given graph is,

From the given graph, the vertices are $A$, $B$, $C$, $X$, $Y$ and $Z$ and the vertex set is $\left\{A,B,C,X,Y,Z\right\}$.

To determine

(b)

To find:

The edge list of given graph.

Answer to Problem 1E

Solution:

The list of edges is $AX$, $AY$, $AZ$, $BB$, $BX$, $BC$, $CX$ and $XY$.

Explanation of Solution

Given:

In the graphical representation of routes, the paths or routes are defined by the lines in the graph. Those lines are the edges of the graph.

The given graph is,

From the given graph, the edges are $AX$, $AY$, $AZ$, $BB$, $BX$, $BC$, $CX$ and $XY$.

To determine

(c)

To find:

The degree of each vertex in given graph.

Answer to Problem 1E

Solution:

The degree on vertices are $\mathrm{deg}\left(A\right)=3$, $\mathrm{deg}\left(B\right)=4$, $\mathrm{deg}\left(C\right)=2$, $\mathrm{deg}\left(X\right)=4$, $\mathrm{deg}\left(Y\right)=2$ and $\mathrm{deg}\left(Z\right)=1$.

Explanation of Solution

In the graph theory, the degree of any vertex is the number of edge formed on that particular vertex.

The count for a loop on any vertex is two degree on that vertex.

Given:

The given graph is,

From the given graph, the vertex A has 3 edges adjoined on it. The degree of vertex A is $\mathrm{deg}\left(A\right)=3$.

The vertex B has 4 edges adjoined on it. The degree of vertex B is $\mathrm{deg}\left(B\right)=4$.

The vertex C has 2 edges adjoined on it. The degree of vertex C is $\mathrm{deg}\left(C\right)=2$.

The vertex X has 4 edges adjoined on it. The degree of vertex X is $\mathrm{deg}\left(X\right)=4$.

The vertex Y has 2 edges adjoined on it. The degree of vertex Y is $\mathrm{deg}\left(Y\right)=2$.

The vertex Z has 1 edge adjoined on it. The degree of vertex Z is $\mathrm{deg}\left(Z\right)=1$.

Conclusion:

Thus, the degree on vertices are $\mathrm{deg}\left(A\right)=3$, $\mathrm{deg}\left(B\right)=4$, $\mathrm{deg}\left(C\right)=2$, $\mathrm{deg}\left(X\right)=4$, $\mathrm{deg}\left(Y\right)=2$ and $\mathrm{deg}\left(Z\right)=1$.

To determine

(d)

To plot:

The version of the graph without crossing points

Answer to Problem 1E

Solution:

The required graph is,

Explanation of Solution

Given:

The given graph is,

The required graph needs to have a route in which no vertex is taken again. From the given graph, the required graph is,