unit 5 part 4

Question 1

minimal spanning tree

Answer 1

all poss links, non neg cost each edge, h subG, sum of all cost edge min
kruskals

Question 2

kruskal algo

Answer 2

till n-1 least edges
not loop
min onwards
highlight only those

Question 3

prims algo

Answer 3

matrix vertices edges cost
min in each column, highlight those
multiple ways

Question 4

dual of a planar graph

Answer 4

.

Question 5

chromatic number

Answer 5

k colors needed properly colored
not less than k
ki of G

Question 6

chromatic number

Answer 6

k colors needed properly colored
not less than k
ki of G

Question 7

consequences of chromatic no.

Answer 7

isolated vertix 1-chromatic
1 or more edges at least 2-chromatic
chrom mo. less than eqil to n
kn => n moe than 1
>= n (subG)
>= subG

Question 8

chrom no. of circle

Answer 8

even -> 2, odd -> 3

Question 9

map coloring

Answer 9

4 color prop

kenneth and wolfgang

Question 10

bipartite chrom ques

Answer 10

.