Graph Theory

Question 1

Graph consists of ?

Answer 1

Vertices and edges

Question 2

Undirected graph?

Answer 2

Edges have no direction

Question 3

degree of a vertex

Answer 3

No. of vertices adjacent to it

Question 4

In degree of a vertex

Answer 4

No. of vertices directed towards a particular vertex

Question 5

Out degree of a vertex

Answer 5

No. of vertices directed away from a particular vertex

Question 6

Sum of degree=

Answer 6

2*no. of edges

Question 7

In directed , sum of out degree=

Answer 7

Sum of in degree = no. of edges

Question 8

outgoing edges denoted by

Answer 8

-

Question 9

incoming edges denoted by

Answer 9

+

Question 10

Undirected graph types

Answer 10

Simple graph and Multigraph

Question 11

Simple graph

Answer 11

No parallel edge, no self loop

Question 12

Multigraph

Answer 12

Parallel edges and self loop present

Question 13

Self loop degree=

Answer 13

2

Question 14

If n vertex simple graph, max and min degree

Answer 14

max-n-1
min-0

Question 15

If n vertex multigraph, max and min degree

Answer 15

max-infinite
min-0

Question 16

Null graph

Answer 16

0 edges

Question 17

Complete graph

Answer 17

All edges in a simple graph
no. of edges=n(n-1)/2

Question 18

Min and max edges in a complete graph

Answer 18

both n(n-)/2

Question 19

min and max edges in null graph

Answer 19

0

Question 20

n-regular graph

Answer 20

all vertices have degree n

Question 21

for k regular graph no. of edges

Answer 21

e=(k*n)/2

Question 22

Complete graph with n vertices can be represented as n-1 regular graph

Answer 22

yes

Question 23

Every cycle graph is a

Answer 23

2-regular graph

Question 24

Cycle graph is not possible for

Answer 24

vertices less than or equal to 2

Question 25

Cycle graph Cn (2-regular graph with n vertices)

Answer 25

n vertices, n edges

Question 26

Wheel graph

Answer 26

Using Cn-1 graph and adding 1 vertex in middle

Question 27

For wheel graph

Answer 27

E=2*(n-1)

Question 28

Bipartite graph

Answer 28

Two groups m & n , no vertex b/w the members of same group

Question 29

In bipartite graph m U n =

Answer 29

V

Question 30

How to verify if graph is bipartite

Answer 30

BFS

Question 31

m intersection n for bipartite

Answer 31

empty set (phi)

Question 32

m can be anything but

Answer 32

empty set or phi

Question 33

n can be anything but

Answer 33

empty set or phi

Question 34

Which graph can never be bipartite

Answer 34

if it contains odd cycle

Question 35

Min. vertex for bipartite

Answer 35

2

Question 36

Min. edges for bipartite

Answer 36

0

Question 37

Complete bipartite graph

Answer 37

When all possible edges present in bipartite graph

Question 38

K2,4

Answer 38

Total edges = 8

Question 39

K m,n

Answer 39

edges= m.n vertices=m+n

Question 40

Suppose you have 10 vertices, max edges complete bipartite =

Answer 40

when divided in half=5*5=25 edges

Question 41

Min. edges in bipartite graph

Answer 41

0

Question 42

Min. edges in complete bipartite graph with n vertices

Answer 42

(n-1).1

Question 43

Min edges in complete bipartite graph with m and n groups

Answer 43

m.n

Question 44

Max edges in bipartite graph

Answer 44

m.n

Question 45

Star graph edges with n vertices

Answer 45

n-1

Question 46

Planar graph

Answer 46

Draw graph w/o crossing any edges(can be represented in one plane)

Question 47

From which complete graph are all complete graphs non planar

Answer 47

K5

Question 48

Non planar requires least how many vertices

Answer 48

5 (one edge causes non planarity, if we remove becomes planar)

Question 49

In complete bipartite graph non planarity starts from

Answer 49

K3,3(one edge causes non planarity, if we remove becomes planar) so K3,4 K4,4 all are non planar

Question 50

Non planarity starts from min. vertices min. edges

Answer 50

V-5 (K5) E-9 (K3,3)

Question 51

A graph G is planar if and only if

Answer 51

it does not contain subgraph which is subdivision of K5 or K3,3

Question 52

Subdivision means

Answer 52

Same structure, only vertices added inside edges

Question 53

See question on copy

Question 54

Regions or faces

Answer 54

Every planar graph is divided into some regions

Question 55

Degree of a region

Answer 55

No. of edges it is bounded by

Question 56

Every edge is used twice in making regions

Answer 56

True

Question 57

Sum of degree of regions =

Answer 57

2*no. of edges

Question 58

See question

Question 59

Euler formula(Connected graph)

Answer 59

|V| + |R| = |E| + 2

Question 60

Euler formula(disconnected graph)

Answer 60

|V| + |R| = |E| + k + 1 (k-no. of connected components)

Question 61

For n vertices how many simple graphs possible

Answer 61

2^(n(n-1)/2)

Question 62

Average degree

Answer 62

Sum of degree/ no. of vertices

Question 63

Average degree bounds

Answer 63

Min degree <= Avg degree <= Max degree

Question 64

Average degree

Answer 64

2 |E| / |v|