CHITKARA

UNIVERSITY

The Graph, Di-Graph & It's Fundamentals

Test Yourself

Capsule 3

1. If a graph has 15 edges, then the sum of the degrees of all the vertices
is
(a) 25 (b) 24 (c) 50 (d) 30
2. The of degrees of all
sum
vertices of a graph is 40. Then the number
of edges is

(a) 20 b) 25 (c) 40 (d) none

3. The sum of degrees of all vertices of a graph is

(a) a prime number (b) an even number

(C) any natural number (d) a perfect square

4. The number of odd vertices in any graph is

(a) odd (b) even

(c) multiple of three (d) none

5. Indicate which of the following is impossible

(a) there exists a graph with 9 odd vertices
(6) there exists a graph with 9 even vertices
(c) sum of degrees of all vertices in a graph is 50
(d) no of edges of a graph is 40
6. If there are 16 edges in a graph, the sum of the degrees of the vertices
1S

(a)8 (b) 16
(c) 32 (d) 64
 CHITKARA
UNIVERSITY

t there are six vertices, nine edges in a graph, then the numder ol

faces is equal to
(a) 5 (b) 15
(c) 3 (d) 2

8. The number of distinct graphs up to three nodes is

(a) 15 (6) 10
(c) 7 (d) 9

9. Draw all the different di-graphs with two vertices.

10. There are Five teams in a tournament. Each team plays each other
team exactly once. Represent the result of each match by a di-graph.

11. Find the number of vertices, the number of edges and the degree of
each vertex in the following undirected graphs. Verify also the
handshaking theorem in each case.

E D

G
G2
12. Find the in-degree and out-degree of each vertex of each of the
following directed graphs. Also verify that the sum of the in-degrees (or
the out-degrees) equals the number of edges.

G
 CHITKARA
UNIVERSITY
13. Consider the directed
graph G =
(V, E) as shown below and
determine the vertex set and
edge set of graph G.

14. Consider the directed

graph as shown below and determine the
in-degree and out-degree of each of vertices of the graph.

15. Find the in-degree and out-degree of each vertex of G.

A

16. Find the in-degree, out-degree and total degree of each vertex of the
following graph.
Na
 CHITKARA
UNIVERSITY

Assignment
1. Detine graph. Explain the different types of graphs with examples.
Graph
Types of Graphs
Undirected Graph
Simple Graph
General Graph
Multi Graph
Pseudograph
Directed Graph
Symmetric Directed Graph
Multiple Directed Graph
Mixed Graph
Finite and Infinite Graph
2. Discuss various graph terminologies.
Degree of Vertex
Pendant Vertex
In-degree and Out-Degree of a Vertex
.Isolated Vertex
Order and Sizeof Graph
Components of Graph
Self-loop
.Loop-free
Parallel Edges
Adjacent Edges
Adjacent Vertices
 CHITKARA
UNIVERSITY

The Graph, Di-Graph & It's Fundamentals

Test Yourself

Capsule 4

Kazimierz Kuratowski

(1896 1980)
Kazimierz Kuratowski was a Polish mathematician and logician.
He was born in Warsaw on February 2, 1896, into an assimilated

Jewish family.
.He was one of the leading representatives of the Warsaw School of
Mathematics.

His contributionsto graph theory include.

The characterization of planar graphs now known as
Kuratowski's theorem.
Identification oftheordered pair (x, y) with the set {{x},
x, y}}
 CHITKARA
UNIVERSITY

Julius Peter Christian Petersen

(1839-1910)
In the mathematical field of Graph Theory, the Petersen Graph is an
undirected graph with 10 vertices and 15 edges. The Petersen Graph is
named after Julius Petersen.

He was a Danish mathematician.

H e was born on June 16, 1839 in Denmark.
.His contributions to the field of mathematics led to the birth of

Graph Theory.

1. A complete graph is

(a) regular (b) connected

(c) simple (d) circuit

2. A complete graph with 8 vertices has

(a) 24 edges (b) 26 edges

(c) 29 edges (d) 28 edges

 CHITKARA
UNIVERSITY

3. The total number of edges in a complete graph with n vertices is

(a) n (b) n-1

(c) n/4 (d) n(n-1)/2
4. The number of
edges in a complete graph Ksis
(a) 10 (b) 15
(c) 25 (d) 7

5. If the degree of each node in an undirected graph is the same, then it

is called

(a) a complete graph (b) a regular graph

(c) a spanning graph (d) none of the above
6. A complete graph must be a

(a) circuit (b) regular graph

(c) non-simple graph (d) null graph

7. The following graph is

A B

(a) complete (b) circuit

(C) regular (d) non-null

8. Show that a complete graph with n vertices consists ofn edges.

edges.
2

9. Find number ofedges in Kio.

10. How many edges are there in Ks7?

 CHITKARA
UNIVERSITY

11. Draw undirected complete graph - Ka and Ko.

12. Draw the complete graph Ki and Ks.

-

13. How many edges has each of the following graphs?

)Ko i)Ka
14. Let G be a r-regular graph where r is an odd integer. Show that the
number of edges of G is a multiple of r.

15. If a simple regular graph has n vertices and 24 edges, find all
possible values of n. Draw a graph against each of such values.

16. For which values of n,m are the following graphs regular?

1. Kn

17. Define regular graph. Can complete graph be a regular graph?

(a) 2- Regular Graph (b) 3-Regular Graph

(a) 4- Regular Graph

18. Draw a regular graph of degree 3.

19. Draw 2-regular graphs of five vertices.

20. Draw a graph which is regular of degree 3 (other than K4 and K3, 3).
 CHITKARA
UNIVERSITY

The Graph, Di-Graph & It's Fundamentals

Test Yourself

Capsule 5

1. Which one
of the following statements is true for the following graph:

(a) complete graph (b) bi-partite graph

(c) circuit (d) none
2. Which one of the following statements is true for the following graph:

(a) complete graph (b) regular graph

(c) bi-partite graph (d) none of these

3. Number of edges of the complete bigraph K3,4 is

(a) 10 (b) 11 (c) 12 (d) none
4. K3,3 is a graph,
(a) with three vertices and three edges
(b) with three vertices and three directed edges
(c) a bi-partite graph with three vertices in each partition
(d) none of the above

5. The edge-set of a null graph is

(a) single-tone set (b) empty set

(c) infinite set (d) none of these
 CHITKARA
UNIVERSITY
H
6. The vertex-set of a null graph is

(a) empty set (b) non-empty set

(c) single-tone set (d) none of these
7. Every vertex of a null graph is

(a) pendant (b) isolated

(c) odd (d) none of these
8. Every vertex of a null graph is
(a) even vertex (b) old vertex
(c) pendant vertex (d) edge-vertex
9. State which of the following graphs are bipartite graphs:
(ii)
N V
B
e
V3

(ii) X

W
10. Draw a complete bipartite graph of K2,3 and K3,3.
11. Consider the graph given below. Is the graph complete? Is it
complete bipartite?
 CHITKARA
UNIVERSITY

12. Prove that a

graph which contains a triangle cannot be bipartite.

13. Draw a
complete bipartite graph on 2 and 4 vertices K24 and 2 and 3
vertices K2,3.
14. Determine whether or not each of the
graph is bipartite. In each case,
give the bipartition sets or explain why the graph is not bipart1te.

15. Draw the bipartite Graphs K24 and K34. Assuming any number of
edges.
16. Draw the complete bipartite Graphs K34 and Ki,5.
17. Draw the complete bipartite graphs K2, 3, K2, 4, and K2, 5.

18. Draw a complete bipartite graph, which is not regular.

19. Draw a graph which is regular but not bipartite.
20. Show that C6 is a bipartite graph.

N3

NA 6
 CHITKARA
UNIVERSITY

21. Deternmine which ofthe graphs given in following figure are bipartite
graphs.
C
a b

f e d
G
a b

d
b

d
G GA
22. Determine whether or not each of the graphs is bipartite. In each
case, give the bipartition sets or explain why the graph is not bipartite.

2
6

4 3
3
(a) 2
(b)

6
(c)