Drawing a Simple Graph With a Certain Number of Vertices

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;