Here, We provide **Graph Theory and Combinatorics GTU Paper Solution Winter 202**2. Read the Full **GT&C GTU paper solution** given below.

**Graph Theory and Combinatorics** **GTU Old Paper Winter 2022 [Marks : 70] : **Click Here

**(a)** Define: Simple Graph, Pseudo Graph, Bipartite Graph.

In graph theory, a graph is a set of vertices or nodes connected by edges or arcs. Here are the definitions of simple graph, pseudograph, and bipartite graph:

- Simple graph: A simple graph is an undirected graph that does not contain any loops or multiple edges. Loops are edges that connect a vertex to itself, while multiple edges are edges that connect the same pair of vertices.
- Pseudograph: A pseudograph is a graph that allows loops and multiple edges. In other words, a pseudograph is a graph that may have edges that connect a vertex to itself or more than one edge connecting the same pair of vertices.
- Bipartite graph: A bipartite graph is a graph whose vertices can be divided into two disjoint sets such that no two vertices within the same set are adjacent. In other words, a bipartite graph is a graph whose vertices can be colored using only two colors such that no two adjacent vertices have the same color. Bipartite graphs are often used to model relationships between two different types of objects, such as employees and projects or students and courses.

**(b)** List properties of Tree.

In graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one path. A tree has the following properties:

- It is an undirected graph with no cycles.
- There is exactly one path between any two nodes.
- It is connected and acyclic.
- Adding an edge between any two vertices will create a cycle.
- Every edge is a bridge.
- A tree with n vertices has exactly n-1 edges.
- The degree of any internal node (a node with degree greater than 1) is at least 2.
- The degree of the root node (a node with degree 1) is 1.
- The sum of the degrees of all the vertices is 2(n-1), where n is the number of vertices in the tree.
- A tree can be represented as a rooted tree with a designated root node.

**(c) **Are the graphs shown in the following figure isomorphic? Justify your answer.

**(a) **How many nodes are necessary to construct a graph with exactly 8 edges in which

each node is of degree 2?

Let n be the number of nodes in the graph.

Each node has degree 2, which means that there are 2 edges coming out of each node. Therefore, the total number of edges in the graph is half the sum of the degrees of all the nodes:

```
total number of edges = (sum of degrees) / 2
```

Since each node has degree 2, the sum of the degrees of all the nodes is just 2n:

```
sum of degrees = 2n
```

Substituting this into the previous equation, we get:

```
total number of edges = (2n) / 2 = n
```

Therefore, for a graph with exactly 8 edges, we need n = 8.

**(b) **What is graph coloring? Explain Greedy coloring.

In graph theory, graph coloring is the assignment of colors to the vertices of a graph such that no adjacent vertices share the same color. The minimum number of colors required to color a graph is called the chromatic number of the graph. Graph coloring has applications in various fields such as scheduling, map coloring, register allocation in compilers, etc.

Greedy coloring is a simple and widely used heuristic algorithm for coloring a graph. The algorithm works by iteratively selecting an uncolored vertex and assigning it the lowest possible color that is not already assigned to any of its neighbors. The algorithm continues this process until all vertices are colored.

The steps of the Greedy coloring algorithm are as follows:

- Initialize an array of colors with all colors set to unassigned.
- Pick an uncolored vertex and assign it the lowest numbered color that is not already assigned to any of its neighbors.
- Repeat step 2 for all remaining uncolored vertices.

Greedy coloring is a simple and easy-to-implement algorithm. However, it may not always produce the optimal solution, i.e., the minimum number of colors required to color the graph. In some cases, the Greedy coloring algorithm may use more colors than necessary. Nonetheless, it is a useful algorithm for practical applications and can be improved upon using various heuristics and techniques.

**(c)****Obtain minimum spanning tree using Primâ€™s algorithm.**

**(c) Describe KÃ¶nigsberg Bridge Problem with respect to graph theory.**

The KÃ¶nigsberg Bridge Problem is a famous problem in graph theory, named after the city of KÃ¶nigsberg (now Kaliningrad, Russia). The city was situated on both sides of the Pregel River and included two large islands connected to each other and the mainland by seven bridges. The problem was whether it was possible to take a walk through the city, crossing each bridge once and only once, and returning to the starting point.

The problem was first posed by the mathematician Leonhard Euler in 1736, who proved that it was impossible to find such a walk. Euler approached the problem using the concept of a graph, where the bridges are represented as edges and the landmasses as vertices. By analyzing the degree of each vertex (the number of edges connected to it), Euler showed that in order to have a walk that crosses each bridge once and only once, each vertex must have an even degree.

In the case of KÃ¶nigsberg, however, there were four vertices with an odd degree, meaning that it was impossible to find such a walk. Euler’s solution to the problem laid the foundation for the field of graph theory and the development of the concept of the Eulerian path and circuit. The KÃ¶nigsberg Bridge Problem remains a classic example of the practical application of graph theory.

**(a) **Differentiate Permutation & Combination with proper example.

Permutation and combination are the two basic concepts of combinatorics used to count the number of possible outcomes. The main difference between permutation and combination lies in the order of selection of objects.

Permutation: A permutation is an arrangement of objects in a specific order. It is denoted as P(n, r) and defined as the number of ways of selecting r objects from a set of n distinct objects, where the order of the selection is important.

For example, let us assume that there are 4 students named A, B, C, and D, and we want to select 2 students from them to form a team. The possible permutations of selecting 2 students from a set of 4 students are AB, AC, AD, BA, BC, BD, CA, CB, CD, DA, DB, and DC. Here, the order of selection is important, so AB and BA are counted as two different permutations.

Combination: A combination is a selection of objects from a set without regard to the order of the objects. It is denoted as C(n, r) and defined as the number of ways of selecting r objects from a set of n distinct objects, where the order of the selection is not important.

For example, using the same set of 4 students named A, B, C, and D, the possible combinations of selecting 2 students from the set are AB, AC, AD, BC, BD, and CD. Here, the order of selection is not important, so AB and BA are counted as one combination.

The formula for permutation and combination are as follows:

- Permutation: P(n, r) = n!/(n-r)!
- Combination: C(n, r) = n!/r!(n-r)!

In summary, permutation and combination are two basic counting principles of combinatorics that have distinct differences in the order of selection of objects.

**(b) **What is Rook Polynomial? Explain expansion formula of it.

In combinatorics, the rook polynomial is a generating function that counts the number of ways to place non-attacking rooks on a chessboard. A rook is a chess piece that can move any number of squares vertically or horizontally. The rook polynomial is a polynomial in two variables: one variable for the size of the chessboard and the other for the number of rooks.

Let R(m,n) be the rook polynomial of an mÃ—n chessboard. The expansion formula for R(m,n) is:

R(m,n) = âˆ‘(-1)^i C(m,i) C(n,i) (m – i)^n

where C(m,i) is the binomial coefficient “m choose i”.

The rook polynomial counts the number of ways to place k non-attacking rooks on an nÃ—n chessboard. The coefficient of the kth degree term in the rook polynomial gives the number of such configurations. The rook polynomial is useful in solving combinatorial problems involving non-attacking rooks, such as the maximum number of non-attacking rooks that can be placed on a chessboard with no two rooks attacking each other.

**(c) **Explain the stable matching problem.

The stable matching problem is a well-known problem in the field of mathematics, economics, and computer science. The problem is essentially a matching problem where a set of men are to be matched with a set of women based on their preferences.

The problem is as follows: There are n men and n women, and each individual has a ranked preference list of the opposite sex. The goal is to find a stable matching between the men and women. A matching is considered stable if there is no pair of individuals who would both prefer each other to their current partners. In other words, a matching is stable if there are no “rogue couples” who would be happier with each other than their current partners.

One algorithm to solve the stable matching problem is the Gale-Shapley algorithm. This algorithm proceeds as follows:

- Initially, all men are free and have not been matched to any woman.
- Each man proposes to the woman he prefers most on his list who has not yet rejected him.
- Each woman considers the proposal from the man she is currently paired with (if any) and the proposal from the man who just proposed to her. She keeps the man she prefers and rejects the other.
- Each rejected man proposes to his next preferred woman who has not yet rejected him.
- The process repeats until every man has been paired with a woman.

The Gale-Shapley algorithm guarantees a stable matching, and it is also efficient as it runs in O(n^2) time.

OR

**(a) **In how many ways a hockey team of eleven can be elected from 16 players?

This problem involves selecting 11 players out of 16, where order does not matter. This can be solved using the combination formula:

nCk = n! / (k! * (n-k)!)

Where n is the total number of players (16) and k is the number of players to be selected (11).

Plugging in the values, we get:

16C11 = 16! / (11! * (16-11)!) = (16 * 15 * 14 * 13 * 12 * 11!) / (11! * 5 * 4 * 3 * 2 * 1) = 8008

Therefore, there are 8,008 ways to select a hockey team of 11 players from 16 players.

**(b) **There are 350 farmers in a large region. 260 farm beetroot, 100 farm yams, 70

farm radish, 40 farm beetroot and radish, 40 farm yams and radish, and 30 farm

beetroot and yams. Let B, Y, and R denote the set of farms that farm beetroot,

yams and radish respectively. Determine the number of farmers that farm

beetroot, yams, and radish.

To determine the number of farmers that farm beetroot, yams, and radish, we need to use the inclusion-exclusion principle.

First, we find the total number of farmers that farm each crop:

- |B| = 260 (number of farmers that farm beetroot)
- |Y| = 100 (number of farmers that farm yams)
- |R| = 70 (number of farmers that farm radish)

Next, we find the number of farmers that farm two crops:

- |B âˆ© R| = 40 (number of farmers that farm both beetroot and radish)
- |Y âˆ© R| = 40 (number of farmers that farm both yams and radish)
- |B âˆ© Y| = 30 (number of farmers that farm both beetroot and yams)

Finally, we find the number of farmers that farm all three crops:

- |B âˆ© Y âˆ© R| = ?

To find |B âˆ© Y âˆ© R|, we need to use the inclusion-exclusion principle:

|B âˆ© Y âˆ© R| = |B| + |Y| + |R| – |B âˆª Y âˆª R| – |B âˆ© R| – |Y âˆ© R| – |B âˆ© Y|

where |B âˆª Y âˆª R| is the number of farmers that farm at least one of the crops.

|B âˆª Y âˆª R| = |B| + |Y| + |R| – |B âˆ© Y| – |B âˆ© R| – |Y âˆ© R| + |B âˆ© Y âˆ© R|

Plugging in the values we know, we get:

|B âˆª Y âˆª R| = 260 + 100 + 70 – 30 – 40 – 40 + |B âˆ© Y âˆ© R|

|B âˆª Y âˆª R| = 320 + |B âˆ© Y âˆ© R|

Substituting back into the first equation, we get:

|B âˆ© Y âˆ© R| = |B| + |Y| + |R| – |B âˆª Y âˆª R| – |B âˆ© R| – |Y âˆ© R| – |B âˆ© Y| |B âˆ© Y âˆ© R| = 260 + 100 + 70 – 320 – 40 – 40 – 30 |B âˆ© Y âˆ© R| = 0

Therefore, there are 0 farmers that farm beetroot, yams, and radish.

**(c) **Describe Hallâ€™s marriage theorem.

Hall’s Marriage Theorem is a fundamental result in graph theory that provides a necessary and sufficient condition for the existence of a perfect matching in a bipartite graph. It states that a bipartite graph with bipartition (X, Y) has a matching that covers all vertices in X if and only if for every subset S of X, the neighborhood N(S) of S (i.e., the set of all vertices in Y that are adjacent to at least one vertex in S) has size greater than or equal to |S|, i.e., |N(S)| >= |S|.

In other words, for a perfect matching to exist, there must be no “blocking sets”, i.e., subsets of X for which the corresponding neighborhood in Y is too small to contain a matching.

The theorem provides a condition for a set of men to be able to each marry a woman, where each woman can only be married to one man. It says that such a matching is possible if and only if every subset of men has at least as many women available to them as there are men in the subset. The theorem has many applications in computer science, economics, and other fields.

This theorem has applications in various fields, including computer science, economics, and social choice theory, where it is used to model matching problems such as stable marriages, job matching, and roommate assignment.

**(a) **Write applications of Transport Network.

Transport networks, which are a type of graph, have various applications in different fields. Here are some examples:

- Transportation and logistics: Transport networks are used in transportation and logistics to model and optimize the flow of goods, people, and vehicles. They help in designing efficient transportation routes, minimizing travel time and distance, and reducing transportation costs.
- Telecommunications: Telecommunication networks use transport networks to model and optimize the flow of data traffic through communication channels. This helps in designing efficient communication networks, minimizing network congestion, and maximizing data transfer rates.
- Power grids: Power grids are complex networks that use transport network concepts to model and optimize the flow of electricity through transmission lines, transformers, and distribution networks. This helps in designing efficient and reliable power grids, minimizing power outages, and reducing energy consumption.
- Water distribution systems: Water distribution systems use transport networks to model and optimize the flow of water through pipes, pumps, and reservoirs. This helps in designing efficient water distribution systems, minimizing water losses, and ensuring equitable water distribution.
- Social networks: Social networks can be modeled as transport networks, where individuals or groups of individuals are connected by social ties. This helps in understanding the structure and dynamics of social networks, identifying key influencers and opinion leaders, and predicting the spread of information or ideas.
- Biological networks: Biological systems, such as food webs, metabolic networks, and gene regulatory networks, can be modeled as transport networks. This helps in understanding the complex interactions and dependencies between different biological entities, predicting the effects of perturbations or interventions, and designing effective treatments for diseases.

**(b) **Give an example of following :

1) A graph that has an Eulerian circuit but no Hamiltonian Circuit

2) A graph that has a Hamiltonian circuit but no Eulerian circuit.

- An example of a graph that has an Eulerian circuit but no Hamiltonian circuit is the following:

```
a --- b
| | \
| | \
c --- d e
```

This graph has an Eulerian circuit `a-b-d-e-c-a`

, which is a closed path that traverses every edge of the graph exactly once. However, it does not have a Hamiltonian circuit, which is a closed path that visits every vertex of the graph exactly once.

- An example of a graph that has a Hamiltonian circuit but no Eulerian circuit is the following:

```
a ----- b
| \ / |
| x |
| / \ |
c ----- d
```

This graph has a Hamiltonian circuit `a-b-d-c-a`

, which visits every vertex of the graph exactly once. However, it does not have an Eulerian circuit, since there is no closed path that traverses every edge of the graph exactly once.

**(c) **Explain the Exponential Generating Function.

In combinatorics and graph theory, the Exponential Generating Function (EGF) is a tool used to count the number of objects with respect to some property or structure. It is a formal power series that encodes the information about the number of objects of different sizes or types.

Suppose that we have a sequence of objects {a_n}, where a_n is the number of objects of size n. The EGF of this sequence is defined as:

â€‹Here, the coefficient of $x^n/n!$ counts the number of objects of size $n$. The EGF has some useful properties, such as linearity, product rule, and composition rule, that make it a powerful tool for solving combinatorial problems.

For example, suppose we want to count the number of labeled graphs with $n$ vertices. We can represent a graph as an adjacency matrix, where the $(i,j)$ entry is 1 if there is an edge between vertices $i$ and $j$, and 0 otherwise. The number of labeled graphs with $n$ vertices can be expressed as the coefficient of $x^n/n!$ in the EGF of the sequence {a_n}, where $a_n$ is the number of labeled graphs with $n$ vertices. Using the product rule, we can write the EGF of {a_n} as:

The coefficient of $x^n/n!$ in the above expression is $\binom{n}{2}$, which is the number of ways to choose 2 vertices from $n$ vertices. Hence, the number of labeled graphs with $n$ vertices is $\binom{n}{2}$, which is well-known result.

In summary, the EGF is a powerful tool for counting combinatorial objects and solving combinatorial problems.

OR

**(a) **Solve the recurrence relation an+1 = 4*an for n>=0, a0=3.

We can solve the recurrence relation using iteration or substitution method.

Using iteration method: a1 = 4*a0 = 4*3 = 12 a2 = 4*a1 = 4*12 = 48 a3 = 4*a2 = 4*48 = 192 a4 = 4*a3 = 4*192 = 768

So, the pattern is an = 4^n * a0 = 4^n * 3.

Using substitution method: an+1 = 4*an => an = 4^(n-1) * a0

Using a0 = 3, we get: a1 = 4*a0 = 4*3 = 12 a2 = 4*a1 = 4*4*3 = 4^2 * 3 a3 = 4*a2 = 4*4^2 * 3 = 4^3 * 3 a4 = 4*a3 = 4*4^3 * 3 = 4^4 * 3

So, an = 4^n * a0 = 4^n * 3.

**(b) **Describe Binomial Theorem.

The Binomial Theorem is a formula for expanding a binomial raised to a positive integer power. Specifically, it states that:

(x + y)^n = C(n,0)x^n*y^0 + C(n,1)x^(n-1)*y^1 + C(n,2)x^(n-2)y^2 + … + C(n,n-1)x^1y^(n-1) + C(n,n)x^0*y^n

where C(n,k) denotes the binomial coefficient “n choose k” and is defined as:

C(n,k) = n! / (k! * (n-k)!)

The formula can also be written more compactly as:

(x + y)^n = âˆ‘ C(n,k) * x^(n-k) * y^k

The Binomial Theorem is useful in combinatorics, probability theory, and other fields that deal with discrete mathematics. It allows us to quickly calculate the coefficients of a binomial expansion, which can represent the outcomes of many different types of events.

**(c) **Explain Catalan numbers with suitable examples.

Catalan numbers are a sequence of natural numbers that appear in many combinatorial problems, particularly those involving the arrangement of objects. They are named after the Belgian mathematician EugÃ¨ne Charles Catalan, who discovered them in the mid-19th century.

The Catalan numbers can be defined recursively or algebraically. The recursive definition is:

C_0 = 1 C_n+1 = sum(C_i * C_n-i) from i=0 to n, for n >= 0

The algebraic definition is:

C_n = (2n choose n)/(n+1), for n >= 0

Here are some examples of problems that are solved using Catalan numbers:

- Parenthesization of expressions: How many ways are there to parenthesize an expression with n terms? For example, the expression a+b+c can be parenthesized in five ways: ((a+b)+c), (a+(b+c)), (a+b)+c, a+(b+c), and (a+b+c). The answer is the nth Catalan number.
- Triangulation of polygons: How many ways are there to triangulate a polygon with n sides using non-intersecting diagonals? The answer is the (n-2)nd Catalan number.
- Mountain ranges: A mountain range is a sequence of up and down steps. How many mountain ranges of length 2n are there that never go below the starting point? The answer is the nth Catalan number.
- Dyck words: A Dyck word of length 2n is a string of n X’s and n Y’s such that no initial segment has more Y’s than X’s. How many Dyck words are there? The answer is the nth Catalan number.

Catalan numbers have many other applications in mathematics and computer science, including the analysis of algorithms, the enumeration of graphs and trees, and the study of pattern avoidance in permutations.

**(a) **Explain de Bruijn graph.

A de Bruijn graph is a directed graph that is widely used in the field of bioinformatics to assemble DNA sequences. It is named after the Dutch mathematician Nicolaas Govert de Bruijn who introduced the concept in 1946.

In a de Bruijn graph, each node represents a k-mer (a string of length k) that is a substring of the DNA sequence. The edges in the graph represent the overlap between two k-mers. Specifically, a directed edge connects two nodes if the k-1 suffix of the first node matches the k-1 prefix of the second node. The resulting graph is a compact representation of all possible k-mers that occur in the DNA sequence, along with their overlaps.

The de Bruijn graph is useful for genome assembly because it allows for the reconstruction of the original DNA sequence from short reads. Given a set of short reads, the de Bruijn graph can be constructed, and then the original sequence can be reconstructed by traversing a path through the graph that covers all nodes exactly once.

**(b) **What is recurrence relation? Explain different types of recurrence relation.

A recurrence relation is an equation that defines a sequence recursively in terms of its previous terms. In other words, it is a way of describing a sequence of numbers by giving a formula for each term in the sequence based on the previous terms. There are several types of recurrence relations, including linear, homogeneous, non-homogeneous, and constant coefficient recurrence relations.

- Linear recurrence relation: A linear recurrence relation is a recurrence relation in which the current term is a linear combination of the previous terms. The general form of a linear recurrence relation is:

an = c1an-1 + c2an-2 + … + ckank

where c1, c2, …, ck are constants and k is the order of the recurrence relation.

- Homogeneous recurrence relation: A homogeneous recurrence relation is a recurrence relation in which the right-hand side of the equation is zero. In other words, the recurrence relation only depends on the previous terms in the sequence.
- Non-homogeneous recurrence relation: A non-homogeneous recurrence relation is a recurrence relation in which the right-hand side of the equation is non-zero. In other words, the recurrence relation depends on both the previous terms in the sequence and some external input or function.
- Constant coefficient recurrence relation: A constant coefficient recurrence relation is a recurrence relation in which the coefficients c1, c2, …, ck are constant for all n. These types of recurrence relations can be solved using various methods, such as the characteristic equation, generating functions, or matrix methods.

**(c) **For the following set of weights construct an optimal binary prefix code. For each

weight in the set give corresponding code word. 5,7,8,15,35,40.

To construct an optimal binary prefix code, we need to follow the Huffman coding algorithm. The steps are as follows:

- Arrange the weights in ascending order.
- Combine the two smallest weights and create a parent node with the combined weight.
- Repeat step 2 until all weights are combined into a single tree.
- Assign 0 to the left branch and 1 to the right branch at each node.
- The code for each weight is the sequence of 0’s and 1’s obtained by traversing the tree from the root to the corresponding leaf node.

Here is the construction process:

Step 1: Arrange the weights in ascending order.

```
5, 7, 8, 15, 35, 40
```

Step 2: Combine the two smallest weights and create a parent node with the combined weight.

```
5+7=12: 5,7 -> 0; 12
8,12 -> 1; 20
15,20 -> 1; 35
35,40 -> 0; 75
```

Step 3: Repeat step 2 until all weights are combined into a single tree.

```
5+7=12: 5,7 -> 0; 12
8,12 -> 1; 20
15,20 -> 1; 35
35,40 -> 0; 75
```

Step 4: Assign 0 to the left branch and 1 to the right branch at each node.

```
75
/ \
0 1
35 \
20
/ \
1 0
15 8
/ \
1 0
5 7
```

Step 5: The code for each weight is the sequence of 0’s and 1’s obtained by traversing the tree from the root to the corresponding leaf node.

```
5: 110
7: 111
8: 10
15: 01
35: 00
40: 11
```

Therefore, the optimal binary prefix code is:

```
5: 110
7: 111
8: 10
15: 01
35: 00
40: 11
```

OR

**(a) **Which trees are complete bipartite graphs?

Complete bipartite graphs are not trees because they contain cycles. However, there is a special type of tree called a “bipartite tree” that is a subgraph of a complete bipartite graph.

A bipartite tree is a tree in which the nodes can be partitioned into two disjoint sets such that no two nodes in the same set are adjacent, and all edges connect a node in one set to a node in the other set.

So, in a complete bipartite graph, any spanning tree that preserves the bipartition of the nodes is a bipartite tree.

**(b) **How summation operator used in generating function?

The summation operator is used in generating functions to represent the coefficients of the power series. Given a generating function, the coefficient of a certain term can be found by taking the derivative of the generating function and evaluating it at the appropriate point.

For example, if f(x) is a generating function and we want to find the coefficient of x^n in the power series expansion of f(x), we can use the following formula:

[ x^n ] f(x) = (1/n!) * [ d^n/dx^n ] f(x)

where [ x^n ] f(x) represents the coefficient of x^n in the power series expansion of f(x), and [ d^n/dx^n ] f(x) represents the nth derivative of f(x) with respect to x.

In other words, the coefficient of x^n is equal to the nth derivative of f(x) divided by n!. This allows us to easily find coefficients of power series without having to explicitly compute each term.

**(c) **Solve the recurrence relation an = an-1 + n with the initial term a0 = 4.

To solve the recurrence relation an = an-1 + n with the initial term a0 = 4, we can use backward substitution method.

First, we have:

a1 = a0 + 1 = 4 + 1 = 5

a2 = a1 + 2 = 5 + 2 = 7

a3 = a2 + 3 = 7 + 3 = 10

a4 = a3 + 4 = 10 + 4 = 14

and so on.

Alternatively, we can use the formula for the nth term:

an = a0 + 1 + 2 + … + (n-1)

This is the sum of the first n natural numbers, which is n(n-1)/2. Substituting a0 = 4, we get:

an = 4 + n(n-1)/2

Therefore, the solution to the recurrence relation an = an-1 + n with the initial term a0 = 4 is:

an = 4 + n(n-1)/2, for n â‰¥ 1.

â€œDo you have the answer to any of the questions provided on our website? If so, please let us know by providing the question number and your answer in the space provided below. We appreciate your contributions to helping other students succeed.”