Combinatorics and Graph Theory: As Per U.P.T.U. Syllabus

Cover......Page 1
Preface
......Page 8
Contents......Page 12
1.1 The Rules of Sum and Product......Page 16
1.2 Permutations......Page 27
1.3 Combinations......Page 40
1.4 Permutations and Combinations with Repetitions......Page 51
1.5 Probability......Page 67
1.6 Ramsey Number......Page 76
1.7 The Catalan Numbers......Page 80
1.8 Group......Page 82
1.9 Generating Function......Page 101
Problem Set 1.1......Page 153
Problem Set 1.2......Page 155
Problem Set 1.3......Page 158
Problem Set 1.4......Page 160
Answers......Page 162
2.1 The First-Order Linear Recurrence Relation......Page 167
2.2 The Second-Order Linear Homogeneous Recurrence Relation with Constant Coefficients
......Page 177
2.3 The Non Homogeneous Recurrence Relations......Page 178
2.4 the Method of Generating Functions......Page 203
Problem Set 2.1......Page 227
Problem Set 2.2......Page 230
Answers......Page 233
3.1 What is a Graph? Definition......Page 235
3.2 Directed and Undirected Graphs......Page 236
3.3 Basic Terminologies
......Page 237
3.4 Degree of a Vertex......Page 238
3.5 Isolated and Pendent Vertices......Page 239
3.6 Types of Graphs......Page 255
3.7 Subgraphs......Page 260
3.8 Graphs Isomorphism
......Page 262
3.9 Operations of Graphs......Page 279
3.10 Connected and Disconnected Graphs
......Page 286
3.11 Walks, Paths and Circuits......Page 293
3.12 Eulerian Graphs......Page 299
3.13 Fleury's Algorithm......Page 309
3.14 Hamiltonian Graphs......Page 313
3.15 Tree......Page 325
3.17 Rooted Tree......Page 326
3.18 Binary Trees......Page 327
3.19 Counting Trees......Page 348
3.20 Minimal Spanning Trees......Page 356
Problem Set 3.1......Page 369
Problem Set 3.2......Page 375
Answers......Page 379
4.3 Unilaterally Connected......Page 381
4.7 Vertex Connectivity......Page 382
4.8 Transport Networks......Page 389
4.9 Max-Flow Min-Cut Theorem......Page 395
4.10 Combinatorial and Geometric Graphs (Representation)
......Page 402
4.11 Planar Graphs......Page 403
4.13 Homeomorphic Graphs......Page 404
4.14 Region......Page 405
4.17 Inner Vertex Set......Page 406
4.19 Crossing Number......Page 407
4.20 Bipartite Graph......Page 408
4.21 Euler's Formula
......Page 410
4.22 Three Utility Problem......Page 420
4.23 Kuratowski's Theorem
......Page 431
4.24 Detection of Planarity of a Graph......Page 432
4.25 Dual of a Planar Graph......Page 438
4.27 Representation of Graphs......Page 447
Problem Set 4.1......Page 456
Problem Set 4.2......Page 461
Answers......Page 465
5.1 Graph Coloring......Page 468
5.2 Chromatic Polynomial......Page 470
5.3 Decomposition Theorem......Page 472
5.4 Color Problem......Page 497
5.5 Matching Theory......Page 501
5.7 Independence......Page 514
5.9 Edge Covering......Page 515
5.11 Line-core and Point-Core......Page 516
5.12 Digraph Definition......Page 517
5.13 Types of Digraphs......Page 519
5.14 Connected Digraphs......Page 522
5.16 Reachability......Page 523
5.19 Arborescence......Page 524
5.20 Hand Shaking Dilemma
......Page 525
5.23 Adjacency Matrix of a Digraph......Page 526
5.24 Nullity of a Matrix......Page 543
5.25 Types of Enumeration......Page 548
5.26 Labeled Graphs
......Page 549
5.28 Generating Functions......Page 552
5.30 Rooted Unlabeled Trees
......Page 553
5.32 Trees Unlabeled Trees
......Page 554
5.34 Permutation......Page 555
5.35 Equivalence Classes of Functions......Page 558
Problem Set 5.1......Page 566
Problem Set 5.2......Page 571
Answers......Page 574
Index......Page 575