Assignment cum worksheet on Graphs

1. Draw graph models, stating the type of graph, to represent airline routes where every
day there are four flights from Boston to Newark, two flights from Newark to Boston,
three flights from Newark to Miami, two flights from Miami to Newark, one flight from
Newark to Detroit, two flights from Detroit to Newark, three flights from Newark to
Washington, two flights from Washington to Newark, and one flight from Washington
to Miami, with
a) an edge between vertices representing cities that have a flight between them (in
either direction).
b) an edge between vertices representing cities for each flight that operates between
them (in either direction).
c) an edge between vertices representing cities for each flight that operates between
them (in either direction), plus a loop for a special sightseeing trip that takes off and
lands in Miami.
d) an edge from a vertex representing a city where a flight starts to the vertex
representing the city where it ends.
e) an edge for each flight from a vertex representing a city where the flight begins to
the vertex representing the city where the flight ends.
Ans:
a) b) c) d)

2. What kind of graph can be used to model a highway system between major cities where
a) there is an edge between the vertices representing cities if there is an interstate
highway between them?
b) there is an edge between the vertices representing cities for each interstate highway
between them?
c) there is an edge between the vertices representing cities for each interstate highway
between them, and there is a loop at the vertex representing a city if there is an
interstate highway that circles this city?
Ans:
a) Simple graph
b) Multigraph
c) Pseudograph
3. Determine whether the graph shown has directed or undirected edges, whether it has
multiple edges, and whether it has one or more loops:

Ans: Multigraph
4. Determine whether the graph shown has directed or undirected edges, whether it has
multiple edges, and whether it has one or more loops:

Ans: Pseudograph
5. Determine whether the graph shown has directed or undirected edges, whether it has
multiple edges, and whether it has one or more loops:

Ans: Directed Graph

6. Determine whether the graph shown has directed or undirected edges, whether it has
multiple edges, and whether it has one or more loops:

Ans: Directed pseudoGraph

7. Construct an influence graph for the board members of a company if the President can
influence the Director of Research and Development, the Director of Marketing, and
the Director of Operations; the Director of Research and Development can influence the
Director of Operations; the Director of Marketing can influence the Director of
Operations; and no one can influence, or be influenced by, the Chief Financial Officer.
Ans:

8. Find the number of vertices, the number of edges, and the degree of each vertex in the
given undirected graph. Identify all isolated and pendant vertices:
 Ans:1.𝒗 = 𝟔;𝒆 = 𝟔;𝒅𝒆𝒈(𝒂) = 𝟐,𝒅𝒆𝒈(𝒃) = 𝟒,𝒅𝒆𝒈(𝒄) = 𝟏,𝒅𝒆𝒈(𝒅) = 𝟎,𝒅𝒆𝒈(𝒆) = 𝟐, 𝒅𝒆𝒈(𝒇) =
𝟑; c is pendent; d is isolated.
2. 𝒗 = 𝟓; 𝒆 = 𝟏𝟑; 𝒅𝒆𝒈(𝒂) = 𝟓, 𝒅𝒆𝒈(𝒃) = 𝟔, 𝒅𝒆𝒈(𝒄) = 𝟓, 𝒅𝒆𝒈(𝒅) = 𝟓, 𝒅𝒆𝒈(𝒆) = 𝟑, Isolated
vertices: none, Pendant vertices: none.
3. 𝒗 = 𝟗; 𝒆 = 𝟏𝟐; 𝒅𝒆𝒈(𝒂) = 𝟑, 𝒅𝒆𝒈(𝒃) = 𝟐, 𝒅𝒆𝒈(𝒄) = 𝟒, 𝒅𝒆𝒈(𝒅) = 𝟎, 𝒅𝒆𝒈(𝒆) = 𝟔, 𝒅𝒆𝒈(𝒇) = 𝟎,
𝒅𝒆𝒈(𝒈) = 𝟒, 𝒅𝒆𝒈(𝒉) = 𝟐, 𝒅𝒆𝒈(𝒊) = 𝟑; d and f are isolated.
9. What does the degree of a vertex represent in the acquaintanceship graph, where vertices
represent all the people in the world? What does the neighbourhood of a vertex in this
graph represent? What do isolated and pendant vertices in this graph represent? In one
study it was estimated that the average degree of a vertex in this graph is 1000. What
does this mean in terms of the model?
Ans: Degree of a vertex = number of acquaintances a person has.
Neighbourhood = the set of all their acquaintances.
Isolated vertex = a person who knows no one.
Pendant vertex = a person who knows exactly one person.
Average degree of 1000 = on average, each person in the world has about 1000
acquaintances.
10. What does the degree of a vertex represent in an academic collaboration graph? What
does the neighbourhood of a vertex represent? What do isolated and pendant vertices
represent?
Ans: The number of coauthors that person has; that person’s coauthors; a person who
has no coauthors; a person who has only one co-author.
11. What do the in-degree and the out-degree of a vertex in a telephone call graph, as
described in Example 8? What does the degree of a vertex in the undirected version of
this graph represent?
Ans:
12. What do the in-degree and the out-degree of a vertex in the web graph, as described in
Example 8?
Ans:
13. Suppose that there are four employees in the computer support group of the School of
Engineering of a large university. Each employee will be assigned to support one of four
different areas: hardware, software, networking, and wireless. Suppose that Ping is
qualified to support hardware, networking, and wireless; Quigley is qualified to support
 software and networking; Ruiz is qualified to support networking and wireless, and Site
is qualified to support hardware and software.
a) Use a bipartite graph to model the four employees and their qualifications.
b) Use Hall’s theorem to determine whether there is an assignment of employees to
support areas so that each employee is assigned one area to support.
c) If an assignment of employees to support areas so that each employee is assigned
to one support area exists, find one.
Ans: a) Parts {h, s, n, w} and {P, Q, R, S},
𝐸 = {{𝑃, 𝑛}, {𝑃, 𝑤}, {𝑄, 𝑠}, {𝑄, 𝑛}, {𝑅, 𝑛}, {𝑅, 𝑤}, {𝑆, ℎ}, {𝑆, 𝑠}}
b) There is.
c) {Pw, Qs, Rn, Sh} among others.
14. Does each of these lists of vertices form a path in the following graph? Which paths are
simple? Which are circuits? What are the lengths of those that are paths?
a) a, e, b, c, b b) a, e, a, d, b, c, a
c) e, b, a, d, b, e d) c, b, d, a, e, c

Ans: a) path, not simple, not a circuit, length 4.

b) not a path
c) a path and a circuit, not simple, length 5.
d) a path and a simple circuit, length 5.
15. Does each of these lists of vertices form a path in the following graph? Which paths are
simple? Which are circuits? What are the lengths of those that are paths?
a) a, b, e, c, b b) a, d, a, d, a
c) a, d, b, e, a d) a, b, e, c, b, d, a

Ans: a) Not a path.

b) Path; circuit; not simple; length 4.
c) Not a path.
d) Not a path.
16. Determine whether the given graph is connected:

Ans: Connected.
17. How many connected components does graph in Exercises 16 have? find each of its
connected components.
Ans: The graph has 1 connected component. The single connected component is the
entire graph itself.
18. What do the connected components of acquaintanceship graphs represent?
Ans: Maximal sets of people with the property that for any two of them, we can find a
string of acquaintances that takes us from one to the other.
19. What do the connected components of a collaboration graph represent?
Ans: The connected components of a collaboration graph represent distinct groups of
people who are all connected through chains of collaborations within their group, but
have no collaborations linking them to people in other groups.
20. Find the strongly connected components of each of these graphs.

Ans: a) {𝒂,𝒆}, {𝒅}, {b}, {𝑐}

b) {𝒂,𝒃,𝒆,𝒇}, {𝑐}, {𝒅} c) {𝒂,𝒊}, {𝒃,𝒉}, {𝑐,𝑔}, {𝒅,𝒇}, {𝑒}

21. Use paths either to show that these graphs are not isomorphic or to find an isomorphism
between these graphs.

Ans: Not Isomorphic

22. Use paths either to show that these graphs are not isomorphic or to find an isomorphism
between them:

Ans: Isomorphic
23. Determine whether the directed graph shown has an Euler circuit. Construct an Euler
circuit if one exists. If no Euler circuit exists, determine whether the directed graph has
an Euler path. Construct an Euler path if one exists.

Ans: No Euler circuit, Euler path exists(𝑎 → 𝑏 → 𝑐 → 𝑎 → 𝑑 → 𝑏 → 𝑑 → 𝑐 → 𝑑).

24. Determine whether the directed graph shown has an Euler circuit. Construct an Euler
circuit if one exists. If no Euler circuit exists, determine whether the directed graph has
an Euler path. Construct an Euler path if one exists.

Ans: Neither
25. For which values of m and n does the complete bipartite graph 𝐾𝑚,𝑛 have an
a) Euler circuit?
b) Euler path?
Ans: 𝒎 ≥ 𝟏, 𝒏 ≥ 𝟏, m and n are even.
26. Determine whether the given graph has a Hamilton circuit. If it does, find such a circuit.
If it does not, give an argument to show why no such circuit exists.

Ans: No. The edge 𝑐 − 𝑓 is a bridge splitting the graph into two 3-vertex components.
A Hamilton circuit would need to cross between the components twice (go and return),
but only one edge 𝑐 − 𝑓 connects them. so a Hamiltonian cycle is impossible.
27. Does the graph in example 26 have a Hamilton path? If so, find such a path. If it does
not, give an argument to show why no such path exists.
Ans: a, b, c, f, d, e is a Hamilton path.
28. Can you find a simple graph with n vertices with n ≥ 3 that does not have a Hamilton
circuit, yet the degree of every vertex in the graph is at least 2 ?
𝑛−1

Ans: for odd 𝑛 the complete bipartite graph above works; for even 𝑛 no such graph
exists (Dirac).
29. Draw a graph with given adjacency matrix.
1 2 1
a) 2 0 0
0 2 2
 0 0 1 1
b)
0 0 1 0
1 1 0 1
1 1 1 0
Ans:
a) b)

30. Represent the given graph using an adjacency matrix.

a) b) c)

Ans:
a) b) c)
0 0 1 0 1 0 2 1
0 0 1 2 0 1 1 2
1 1 0 1 2 1 1 0
0 2 1 0 1 2 0 1

31. Represent each of these graphs with an adjacency matrix.

a) 𝐾4
b) 𝐾1,4
c) 𝐾2,3
d) 𝑄 3
Ans:
a) b) c) d)
 32. Let G be a simple graph with n vertices. Show that G is tree if and only if it is connected
and has 𝑛 − 1 edges.
33. Use an incidence matrix to represent the given graphs.

a) b) c)

Ans:
a) b) c)

34. Show that isomorphism of simple graphs is an equivalence relation.

35. Show that this graph is self-complementary.

36. Are the simple graphs with the following adjacency matrices isomorphic?
0 0 1 0 1 1
a) 0 0 1 , 1 0 0
1 1 0 1 0 0
0 1 0 1 0 1 1 1
b) 1 0 0
,
1 1 0 0 1
0 0 0 1 1 0 0 1
1 1 1 0 1 1 1 0
0 1 1 0 0 1 0 1
c) ,
1 0 0 1 1 0 0 0
1 0 0 1 0 0 0 1
0 1 1 0 1 0 1 0
Ans: a) Yes b) No c)No
37. Show that if G is a connected graph, then it is possible to remove vertices to disconnect
G if and only if G is not a complete graph.
38. Suppose that a connected planar graph has six vertices, each of degree four. Into how
many regions is the plane divided by a planar representation of this graph?
Ans:8
39. Show that a simple graph that has a circuit with an odd number of vertices in it cannot
be colored using two colors.
40. Find the chromatic number of the given graph.
a) b)

Ans: a) 3 b) 3
41. What is the chromatic number of 𝑊 𝑛?
Ans: 3 if n is even, 4 if n is odd.
42. The mathematics department has six committees, each meeting once a month. How
many different meeting times must be used to ensure that no member is scheduled to
attend two meetings at the same time if the committees are 𝐶 1 =
{𝐴𝑟𝑙𝑖𝑛𝑔ℎ𝑎𝑢𝑠, 𝐵𝑟𝑎𝑛𝑑, 𝑍𝑎𝑠𝑙𝑎𝑣𝑠𝑘𝑦},𝐶 2 = {𝐵𝑟𝑎𝑛𝑑,𝐿𝑒𝑒, 𝑅𝑜𝑠𝑒𝑛}, 𝐶 3 =
{𝐴𝑟𝑙𝑖𝑛𝑔ℎ𝑎𝑢𝑠, 𝑅𝑜𝑠𝑒𝑛, 𝑍𝑎𝑠𝑙𝑎𝑣𝑠𝑘𝑦}, 𝐶 4 = {𝐿𝑒𝑒, 𝑅𝑜𝑠𝑒𝑛, 𝑍𝑎𝑠𝑙𝑎𝑣𝑠𝑘𝑦}, 𝐶 5 =
{𝐴𝑟𝑙𝑖𝑛𝑔ℎ𝑎𝑢𝑠,𝐵𝑟𝑎𝑛𝑑} and 𝐶 6 = {𝐵𝑟𝑎𝑛𝑑,𝑅𝑜𝑠𝑒𝑛, 𝑍𝑎𝑠𝑙𝑎𝑣𝑠𝑘𝑦}?
Ans: 5
43. Find the edge chromatic numbers of
a) 𝐶 𝑛, where 𝑛 ≥ 3
b) 𝑊 𝑛, where 𝑛 ≥ 3
Ans: a) 2 if n is even, 3 if n is odd b) n
44. Show that if 𝐺 is a graph with 𝑛 vertices, then no more than 2 edges can be colored the
𝑛

same in an edge coloring of 𝐺.

45. Show that Graphs G1, G2, G3 all homeomorphic.

46. Use Kuratowski’s theorem to determine whether the given graph is planar.
a) b)
 Ans: a) Planer b) Non planer
47. Suppose that a connected planar simple graph with 𝑒 edges and 𝑣 vertices contains no
simple circuits of length 4 or less. Show that 𝑒 ≤ ( 3 )𝑣 − ( 3 ) if 𝑣 ≥ 4.
5 10

48. Which of these non-planer graphs have the property that the removal of any vertex and
all edges incident with that vertex produces a planar graph?
a) 𝐾5 b) 𝐾6 c) 𝐾3,3 d) 𝐾3,4
Ans: Only a) and c)
49. How many subgraphs with at least one vertex does 𝐾3 have?
Ans: 17
50. Draw all subgraphs of this graph.

51. Which of this graphs are trees?

Ans: a), c) and e)

52. Answer these questions about the rooted tree illustrated.
 a) Which vertex is the root?
b) Which vertices are internal?
c) Which vertices are internal?
d) Which vertices are children of j?
e) Which vertex is the parent of h?
f) Which vertices are siblings of o?
g) Which vertices are ancestors of m?
h) Which vertices are descendants of b?
Ans: a) a b) a, b, c, d, f, h, j, q, t c) e, g, i, k, l, m, n, o, p, r, s, u d) q, r e) c f) p
g) f, b, a h) e, f, l, m, n
53. Show that a simple graph is a tree if and only if it is connected but the deletion of any
of its edges produces a graph that is not connected.
54. Use Prim’s algorithm to find a minimum spanning tree in the graph.

Ans:

55. Use Kruskal’s algorithm to find a minimum spanning tree in the weighted graph.
 Ans:

56. Show that there is a unique minimum spanning tree in a connected weighted graph if
the weights of the edges are all different.
57. Find a connected weighted simple graph with the fewest edges possible that has more
than one minimum spanning tree.
Ans:

58. Use Kruskal’s algorithm to find a minimum spanning tree for the weighted graph.

Ans: {e, f }, {a, d}, {h, i}, {b, d}, {c, f }, {e, h}, {b, c}, {g, h}
59. Use Dijkstra’s algorithm and Floyd-Warshal algorithms to produce a minimum
spanning tree for the weighted graph given below.
 a)

b)

Ans:
a)

b)

60. Build a binary search tree for the words banana, peach, apple, pear, coconut, mango,
and papaya using alphabetical order.
Ans: