Name: Arjeanette S.

Delmo Prog/Section: BS PSYCHOLOGY 1-A-2

Instructor: Mr. Julieto Comendador Jr. Date: January 5, 2021

Activity A Graph Theory

A. Consider the following graphs:

Graph A Graph B

1.) Which of the following vertex sequence describe paths in the graph given above?
a.) STUVWXZY - ✓ Graph B
b.) TVWZY - X
c.) STUS - ✓ Graph B
d.) UYVTXZYU - ✓ Graph A
e.) WVUSTVW - ✓ Graph B

2.) Which paths in no.1 are closed paths? Cycles?

CLOSED PATHS
c. STUS
e. WVUSTVW
- They are closed paths because their last vertices are the same.
CYCLES
c. STUS
e. WVUSTVW
- These paths are cycles because their paths are closed, no edges were repeated, and all their
vertices, except for their first and last vertices, are distinct.

3.) From the graph above determine the vertex sequence of the shortest path connecting the following
pairs of vertex and give each length:
GRAPH A GRAPH B
a. S & Z SWZ (length = 2) SUVWYZ (length = 5)
STVWXZ (length = 5)
 b. S & V SV (length = 1) STV (length = 2)
SUV (length = 2)
c. U & Y UY (length = 1) UVWY (length = 3)
d. U & X UYZX (length = 3) UVWX (length = 3)
USTX (length = 3)
e. V & W VZW (length = 2) VW (length = 1)
VTW (length = 2)
4.) For each pair of vertex in no. 3 give the vertex sequence of the longest path connecting them that
repeat no edges. Is there a longest path connecting them?
YES, there is a longest past connecting them.
GRAPH A GRAPH B
a. S & Z SWYUSVTXZ (length = 8) STUVWXZ (length = 6)
b. S & V SUYWSTXZYV (length = 9) STUV (length = 3)
c. U & Y USTVSWTXZVY (length = 10) USTUVWXYZ (length = 8)
d. U & X USTVSWYVZWTX (length = 11) UTSUVWYZX (length = 8)
e. V & W VSUYZXTVZW (length = 9) VUSTVW (length = 5)

5.) How many spanning trees are can be generated from its graph? Define 2 spanning trees of Graph A
and B.
According to geeksforgeeks.org, if a graph is a complete graph with n vertices, then total
number of spanning trees is n(n-2) where n is the number of nodes in the graph. Since GRAPH A and
B are complete graphs and they have the same number of vertices, both of them can generate 262,
144 spanning trees.
According to the lesson given in Canvas, if a graph has an n-edges, then there are n! spanning
trees in the graph. GRAPH A has 14 edges, therefore, 14! = 87, 178, 291, 200 spanning trees. On the
other hand, GRAPH B has 13 edges, therefore, 12! = 479, 001, 600 spanning trees.
6.) Which graph has and Euler path? Euler Circuit? (Use Fleury’s Algorithm) For those that don’t give an
explanation?
GRAPH A has a Euler Path and Euler Circuit. Vertex Sequence = ZYVSUYWSTWZVTXZ
GRAPH B also has a Euler Path because it can use each edge exactly once. GRAPH B has no Euler
Circuit because two of its vertices have odd degree.

7.) Which graph contains Hamiltonian Path? Hamiltonian Circuit? For those that don’t give an
explanation?
GRAPH A has Hamiltonian Path and Hamiltonian Circuit.
GRAPH B has Hamiltonian Path but doesn’t have Hamiltonian Circuit because if it will duplicate its
first vertex, it cannot use each vertex only once.

B. Determine whether the following graphs are planar.

Graph 1 Graph 2
GRAPH 1 is NOT a Planar Graph because it cannot be redrawn without its edges crossing.
GRAPH 2 is A Planar Graph because it can be redrawn without its edges crossing.
 C. Consider the graph below.
a.) Construct the Matrix Representation of the Graph.
b.) Determine whether the graph is simple or not. If it is a simple the adjacency matrix of the graph
and determine the no. of paths of length 2 that it has.

A B C D E F A B C D E F
A B C D E F A 0 1 1 1 0 1 A 0 1 1 1 0 1
A 0 1 1 1 0 1 B 1 0 1 0 1 0 B 1 0 1 0 1 0
M= B 1 0 1 0 1 0 MxM =
C 1 1 0 1 0 1 X C 1 1 0 1 0 1
C 1 1 0 1 0 1 D 1 0 1 0 1 1 D 1 0 1 0 1 1

D 1 0 1 0 1 1 E 0 1 0 1 0 1
E 0 1 0 1 0 1
E 0 1 0 1 0 1 F 1 0 1 1 1 0
F 1 0 1 1 1 0
F 1 0 1 1 1 0

A B C D E F
4+3+4+4+3+4+1+3+2+3+2+1+3+0+3+
A 4 1 3 2 3 2
2+3+2+1+3+1 = 52
B 1 3 1 3 0 3 52 PATHS
M2 = C 3 1 4 2 3 2
D 2 3 2 4 1 3 It is a SIMPLE GRAPH.
E 3 0 3 1 3 1
F 2 3 2 3 1 4
Name: Arjeanette S. Delmo Prog/Section: BS PSYCHOLOGY 1-A-2
Instructor: Mr. Julieto Comendador Jr. Date: January 5, 2021

Activity B Graph Theory

A. Suppose that the diagram below represents the floor plan for the ground of an art museum. Is it
possible to tour the exhibit on the first floor so that you pass through each door exactly
once?(Source: D.S.Malik and M.K. Sen) Support your answer.

No, because there will be always either one door that cannot be
used or one door that will be used twice.

B. The IT department is about to create a network to connect all the computer terminals in their
office. The floor plan is shown below:
The location of computer terminals are represented by the following capital letters and their respective
distances to their adjacent terminal is shown in the table below:

Adjacent Distance
Computers (in meters)

A&B 7

A&E 5

B&C 6

B&F 5

C&G 5

C&D 8

D&H 6

E&B 9

E&F 8

E&I 3

F&G 4

F&M 8

G&M 9

G&H 10

H&K 2

H&J 5

I&L 3

I&M 11
 J&M 9

J&K 7

K&T 8

L&N 4

L&M 10

M&Q 5

M&R 7

M&S 10

N&O 6

N&Q 12

Q&R 7

R&S 8

S&T 10

Determine the minimum length of cable wire required in the construction of the network in their office.
How much will it cost the cable required if 1 meter of cable is 30 pesos?

100 meters x 30 pesos = 3, 000 pesos

The cables will cost 3, 000 pesos because 100 meters is the minimum length of cable wire required to
construct the network in their office and 1 meter of cable costs 30 pesos.

C. Prepare a list of the names of your 10 friends and your common friends in Facebook. Construct a
graphical representation of your friend and your common friends. Prepare a matrix representation
of your constructed graph. Who among you has the most number of friends?
D. Using the Four Color Theorem, to color the different cities in NCR.