SNHU MAT 230 Discrete Mathematics Module Eight Homework Solutions

This document contains the solutions to a MAT 230 Discrete Mathematics homework assignment, focusing on graph theory concepts. The solutions address questions related to Euler circuits and Euler paths, analyzing the degrees of vertices in given graphs to determine the existence of these paths a...Read More

Running head: MATHEMATICS 1
Discrete Mathematics
Name
Institution

MATHEMATICS 2
Solutions
Question 1
From the above diagram, the degrees of the vertices are 2, 4, 5, and 3. Euler Circuit is a
connected multi-graph that has a minimum of two vertices with an even degree of vertices. From
the graph above, it therefore shows that there is no Euler Circuit because there is an odd degree
of 5 and 3 vertices. On the other hand, Euler path is the condition to which a multi-connected
graph posses exactly two odd degree of vertices (Ismail et al., 2009). From the graph above,
there is an Euler path with only two odd degrees of 5 and 3 thus the graph contains no Euler
circuit.
Question 2
Generally, a complete graph is defined has one that has full pair of the vertices with an
adjacent pairs. In addition, the adjacent pair vertices are only complete if their edge is between
two vertices. With n vertices, a graph is said to be have the following elements with Kn;

MATHEMATICS 3
a. There exists n vertices from the Kn . This is because each vertex from n is directly
adjacent to the opposite vertex. As a result, there is n-1 vertex degree.
b. Assuming that the number of edges in Kn , and d(Qi) = n-1 for i=1, 2,…n is equal to E,
then by hand shaking theory, we can get the summation of vertices to be two times the
numeral value of the total edges. It can therefore be calculated as follows;
∑
i=1
n
deg ree ( Qi )=2 E
∑
i=1
n
( n−1 )=2 E
n (n-1) =2E
E = n(n−1)
2
Resulting in to the number of edges in Kn to be n (n-1).
Question 3
By definition, Euler path is that path which uses every edge of a path without a repetition.
Conversely, an Euler circuit is a circuit that exploits all edges without repetition. From the above
definition, we can therefore say that the graph G below posses only Euler path if it confirms to
the condition that there is only two odd degree vertices. I addition, the graph G below can only
be confirmed to possess an Euler circuit if it has no odd degree of vertex (Dvořák et al., 1997).
Considering the below graph;

MATHEMATICS 4
From the above graph, U3, U4, U6, and U7 vertices are of degree 5, 3, 3, and 3 respectively.
With more than two vertices of odd degree, we can conclude that the graph has no Euler path. In
addition, from the graph above, there exists at least one vertex of odd degree thus confirming that
there is no presence of Euler circuit. As a result, the above graph is said to have neither Euler
path nor Euler circuit.
Question 4
From the given graph above, the following features can be noted;
a) 1 vertex of degree 2
b) 1 vertex of degree 3
c) 2 vertices of degree 4
d) 1vertex of degree 5

MATHEMATICS 5
From the above features, we can then define the presence of either Euler circuit or Euler Path, or
both. As a result, there is no existence of Euler circuit. This is because for the presence of Euler
circuit, there should be an even degree but with no even degree as per the features above, the
Euler circuit is said to not be present. In addition, for the presence of Euler path in graph G
above, there should be exactly two vertices with odd degree. However, given that the graph
above has odd degree with exactly two vertices i.e. (3,5), then there exits an Euler path.
Question 5

MATHEMATICS 6
References
Dvořák, T., Havel, I., & Liebl, P. (1997). Euler cycles in the complete graph K2m+ 1. Discrete
Mathematics, 171(1-3), 89-102.
Ismail, A. S., Hasni, R., & Subramanian, K. G. (2009). Some applications of Eulerian
graphs. International Journal of Mathematical Science Education, 2(2), 1-10.