Homework4
TRAN HAI DANG
March 25, 2024
10.1
2
a) A simple graph is the most appropriate since it has no loop or parallel edge
and the edges are undirected.
b) A multigraph would be suitable because there may be more than 1 interstate
between those cities.
c) the pseudograph as the discription said it can go in circle.
3
this graph has no loop, undirected edges don’t have multi-edges ⇒ simple graph
4
this graph has no loop, undirected edges but it has multi-edge ⇒ multigraph.
7
this graph has loops, directed edges multi-edges ⇒ directed multigraph.
8
his graph has loops, directed edges multi-edges ⇒ directed multigraph.
12
As this graph has loop ⇒ it is reflexive and this is a undirected graph so that
it’s verticles have edge between them ⇒ it’s also symmetric.
1
13
c)
A2 A5
A1 A4
A3 A6
10.2
4
1) Apply the formula the sum of degree = 2m with m is the numbers of edges
⇒ 2.6=12
2) Apply the formula the sum of degree = 2m with m is the numbers of edges
⇒ 2.13=26
3)Apply the formula the sum of degree = 2m with m is the numbers of edges
⇒ 2.12=24
5
Since the simple graph don’t allow multi edges and the task required 15 vertices
with the degree [Link] sum of degree will be 75. According to the handshaking
lemma the numbers of edges will be 37.5 but the number of edges must be integer
so the answer is no
6
According to the handshaking lemma: 2m=sum of the degree so that the total
numbers of people has shaken hand = numbers of handshake are always even
2
9
vertices:5
edges:13
deg − a=6
deg + a=1
deg − b=1
deg + b=5
deg − c=2
deg + c=5
deg − d=4
deg + d=2
deg − e=0
deg + e=0
12
In the acquaintanceship graph, where vertices represent all the people the degree
of a vertex represent how many people that one’s person [Link] it’s a isolated
vertex , that person don’t know anyone.A pendent vertex is the one who only
know 1 [Link] neighborhood means that the vertex u knows everyone. The
average degree is 1000 means an average person known 1000 people, in the world
26
a) Because Kn there always an edge between 2 vertices so that Kn is only
bipartite at n=2
b) First we need n¿2 with n is an integer so that Cn can be defined. If n is even
Cn will bipartite
c) Every wheel is bipartite
d) Qn is bipartite for all n¿0 , since we can divide the vertices into these two
classes: those bit strings with an odd number of 1’s , and those bit strings with
an even number of 1’s .
67
Since G is a simple graph so that G’ also a simple graph and G ∨ G′ is also a
simple graph
As the complementary graph G’ has the same vertices as G so their union will
also has n vertices.
Because every edges which are not presented in G will be presented in G’ ⇒
every 2 vertices will have an edge between them ⇒ so it will be Kn
3
10.3
4
Initial vertex terminal vertices
a b,d
b a,c,d,e
c b,c
d a,e
e c,e
8
0 1 0 1 0
1 0 1 1 1
0 1 1 0 0
1 0 0 0 1
0 0 1 0 1
10
A2
A1
A3
4
16
A2
A1
A3
26
a) density=(2x)/(y(y-1)) with x is numbers of edges and y is number of vertices
dens=(2 ∗ 5)/(6 ∗ 5) = 1/3
b)dens=(2 ∗ 24)/(16 ∗ 15) = 1/5
c)dens=(2 ∗ 12)/(8 ∗ 7) = 3/7
32
For undirected graph:sum of a row is the number of edges incident to vertex i
or the degree of the vertex i.
For directed graph: that is the number of out degrees of i vertex
33
This is the same answer as ques 32.
34
The sum of the entries in the ith row of the incidence matrix is the number of
edges incident to vertex i, since there is one column with a 1 in row i for each
such edge.
35
The entries in column j of the incidence matrix represent the number of vertices
that edge ej is incident to. If ej is a loop then the sum of entries in column j
5
will be 1 ; if it not a loop then the sum of entries will be 2
56
if G is isomorphic the number of edges of the union of them :|E(G ∨ G′ )| =
(n ∗ (n − 1))/2 so that|E(G)| = (n ∗ (n − 1))/4
57
58
a)with 2 vertices there will be 2 nonisomorphic graphs
b)with 3 vertices there will be 4 nonisomorphic graphs
c)with 4 vertices there will be 1 nonisomorphic graphs
59
As there are only 3 edges so that i only consider that it’s only has 3 vertices are
being using ⇒ 4 nonisomorphic graphs.
60
74
Due to Graph Theory by Frank Harary (Addison-Wesley, 1969):
a)10
b)104
c)3069