Discrete Mathematics

Running head: DISCRETE MATHEMATICS 1
Discrete Mathematics
By (Name of Student)
(Institutional Affiliation)
(Date of Submission)

1: (2 points each). Give clear and concise definition of the following:
a. A simple graph
A simple graph in a discrete mathematics refers to a collection of points called vertices and
lines between those points called edges.
b. The degree of a vertex
The degree of a vertex under undirected graph refers to the number of edges incident with it,
except that a loop at a vertex contributes two to the degree of that vertex. In most cases, the
degree of the vertex v is usually denoted by deg (v).
c. Adjacent vertices
Under the graph theory, an adjacent vertex v in a graph is a vertex that is connected to v by
an edge.
d. A complete graph
A complete graph in the mathematical field of graph theory is a simple undirected graph in
which every pair of the distinct vertices is connected by a unique edge.
e. A bipartite graph
A bipartite graph, also known as a bigraph, is a set of graph vertices decomposed into disjoint
sets in such a way that no two graph vertices within the same set are adjacent
f. A graph isomorphism
A graph isomorphism is the mapping from the vertices of the given back to vertices of such
that the resulting graph is isomorphic with.
g. Two undirected graphs G and H are homeomorphic if and only if

Two undirected graphs G and H are homeomorphic if and only if G → H and H → G. That if
and only the mapping from the vertices of G to H given back to the vertices of H.
(1 Point each). Answer the following questions as True or False
h. Answer: TRUE
i. Answer: TRUE
j. Answer: TRUE
k. Answer: FALSE
l. Answer: TRUE
m. Answer: TRUE
2: (6 points)
a. For which values of m and n does the complete bipartite graph Km,n have an Euler
circuit?
The graph will only have an Euler circuit in this case if and only if m and n are both even and
for this case, value of m=n
b. What is the degree of each vertex in the complete graph on n vertices, Kn?
The degree of each vertex in a complete graph on n vertices, Kn is (n-1)
c. How many edges does Kn have?
The number of edged of Kn is [n (n-1)] / 2