Discrete Math for Computer Science  Assignment # 6

CS201: Discrete Math for Computer Science
 Assignment # 6
Due: May 31st, at the beginning of class
Q.1 Which of these are posets?
(a) (R, =)
(b) (R, <)
(c) (R, ≤)
(d) (R, 6=)
Q.2 Answer these questions for the partial order represented by this Hasse
diagram.
a b c
d e f
i h g
j k
l m
Figure 1: Q.2
(a) Find the maximal elements.
(b) Find the minimal elements.
(c) Is there a greatest element?
(d) Is there a least element?
(e) Find all upper bounds of {a, b, c}.
1
(f) Find the least upper bound of {a, b, c}, if it exists.
(g) Find all lower bounds of {f, g, h}.
(h) Find the greatest lower bound of {f, g, h}, if it exists.
Q.3 Let G be a simple graph with n vertices.
(a) What is the maximum number of edges G can have?
(b) If G is connected, what is the minimum number of edges G can have?
(c) Show that if the minimum degree of any vertex of G is greater than or
equal to (n − 1)/2, then G must be connected.
Q.4 Let n ≥ 5 be an integer. Consider the graph Gn whose vertices are the
sets {a, b}, where a, b ∈ {1, . . . , n} and a 6= b, and whose adjacency rule is
disjointness, that is, {a, b} is adjacent to {a
0
, b0} whenever {a, b}∩{a
0
, b0} = ∅.
(a) Draw G5.
(b) Find the degree of each vertex in Gn.
Q.5 Let G = (V, E)s be a graph on n vertices. Construct a new graph,
G0 = (V
0
, E0
) as follows: the vertices of G0 are the edges of G (i.e., V
0 = E),
and two distinct edges in G are adjacent in G0
if they share an endpoint.
(a) Draw G0
for G = K4.
(b) Find a formula for the number of edges of G0
in terms of the vertex
degrees of G.
Q.6 Let G be a connected graph, with the vertex set V . The distance between
two vertices u and v, denoted by dist(u, v), is defined as the minimal length
of a path from u to v. Show that dist(u, v) is a metric, i.e., the following
properties hold for any u, v, w ∈ V :
(i) dist(u, v) ≥ 0 and dist(u, v) = 0 if and only if u = v.
2
(ii) dist(u, v) = dist(v, u).
(iii) dist(u, v) ≤ dist(u, w) + dist(w, v).
Q.7 Show that if G is bipartite simple graph with v vertices and e edges,
then e ≤ v
2/4.
Q.8
(a) What is the sum of the entries in a row of the adjacency matrix for an
undirected graph? For a directed graph?
(b) What is the sum of the entries in a column of the adjacency matrix for
an undirected graph? For a directed graph?
Q.9 Show that isomorphism of simple graphs is an equivalence relation.
Q.10 Show that every connected graph with n vertices has at least n − 1
edges.
Q.11 Explain how to find a path with the least number of edges between two
vertices in an undirected graph by considering it as a shortest path problem
in a weighted graph.
Q.12 Which of the these nonplanar graphs have the property that the removal
of any vertex and all edges incident with that vertex produces a palnar graph?
a) K5 b) K6 c) K3,3 d) K3,4
3