Discrete Mathematics Assignment: Definitions, Theorems, and Proofs

This document presents a complete solution to a discrete mathematics assignment. The solution covers various core concepts in graph theory, including definitions of simple graphs, degrees of vertices, adjacent vertices, complete graphs, bipartite graphs, graph isomorphisms, and homeomorphic graphs. The assignment includes true/false questions, problem-solving involving Euler circuits, degrees of vertices in complete graphs, and the number of edges in complete graphs. It also addresses Euler's formula, bipartite planar graphs, and proofs related to Kuratowski's graph. The assignment further explores Hamilton paths, Euler circuits and paths in multigraphs, and poset analysis, including identifying maximal and minimal elements, greatest and least elements, and topological sorting. References to key texts in discrete mathematics are also provided.

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

3: (6 points)
a. We are given v= 8, and each vertex has degree three, so the sum of all degrees is 24.By
the Handshaking Theorem, 2e= 24, so e= 12. Euler’s Formula gives us r= 2 = 8 + 12 =
6.
Thus the number of regions are 16
b.
In a bipartite planar simple graph, the smallest region would have at least 4 edges in
its boundary. Since every edge can be used in the limits of two regions, we have 4r ≤
2e → r ≤ e 2. By substitution this into Euler’s formula, we have v + e 2 − e ≥ 2 v − 2
≥ e 2
Therefore e ≤ 2v − 4.

c. Proof that that K4,2
In K4, 2 we have v = 8 and e = 10 and under Kuratowski's graph is planar if and only if does
it contains a sub-graph that is homeomorphic.
4: (4 points)
The simple graph shown have no Hamilton path. This is because it has disconnected vertices
G, H and I. The vertices G, H and I are disjoin and undirected. For the figure to have a
Hamilton path, the path must be undirected once at each point (vertex) but for our case, the
path is not directed to any vertex only once.

5: (4 points)
The multi-graph has both an Euler circuit and the Euler path. The Euler circuit is A, B and E
while the Euler path is; A →E →B →C →D
6. (10 points)
a.
. b.
Answer each question for the above poset
i. What are the maximal elements?
The maximal elements are; {1, 2, 30}
ii. What are the minimal elements?
The minimal elements are: {2, 3, 6, 9, 36, 45}
Iii, Is there a greatest element?
Yes, the greatest element is {1}
iv. Is there a least element?
1
30 9 1
0
45 36
4
5
4
5

The least element is {36}
c. Write down a topological sort for this poset
(1, 2), (3, 6), (30, 36)
References
Ne, J. (2009). Invitation to discrete mathematics. Oxford University Press.
Sylvester, G., & John T. (2012). Graph Theory: discrete mathematics. Springer Science &
Business Media.
Skiena, S. S., & Bhansali, A. (2015). Implementing discrete mathematics: Combinatorics and
graph theory with Mathematica (Vol. 52). Reading, MA: Addison-Wesley.