GATE CS & IT Engineering Engineering Mathematics Syllabus

When does a connected graph have an Eulerian path (but not necessarily a circuit)?

When exactly zero or two vertices have odd degree. If two are odd, the path starts at one odd vertex and ends at the other.

Define vertex connectivity $\kappa(G)$ and edge connectivity $\lambda(G)$, and state Whitney's inequality.

$\kappa(G)$ is the minimum number of vertices whose removal disconnects $G$; $\lambda(G)$ is the minimum number of edges. Whitney: $\kappa(G) \leq \lambda(G) \leq \delta(G)$, where $\delta(G)$ is the minimum degree.

State König's theorem relating matching and vertex cover in bipartite graphs.

In a bipartite graph, the size of a maximum matching equals the size of a minimum vertex cover.

What is an augmenting path, and how is it used to find a maximum matching?

An augmenting path is a path that alternates between non-matching and matching edges and begins and ends at unmatched vertices. Flipping its edges increases the matching size by one; a matching is maximum iff no augmenting path exists (Berge's theorem).

Define the chromatic number $\chi(G)$ of a graph.

$\chi(G)$ is the minimum number of colors needed to color the vertices so that no two adjacent vertices share the same color.

What is the chromatic number of a bipartite graph (with at least one edge) and of a complete graph $K_n$?

A bipartite graph with at least one edge has $\chi = 2$; the complete graph has $\chi(K_n) = n$.

State the Four Color Theorem.

Every planar graph can be properly vertex-colored with at most $4$ colors, i.e. $\chi(G) \leq 4$ for planar $G$.

State Brooks' theorem giving an upper bound on the chromatic number.

For a connected graph that is neither a complete graph nor an odd cycle, $\chi(G) \leq \Delta(G)$, where $\Delta(G)$ is the maximum degree.

How many spanning trees does the complete graph $K_n$ have (Cayley's formula)?

$n^{n-2}$.

Give the formula for the number of $r$-combinations and $r$-permutations of $n$ distinct objects.

Combinations: $\binom{n}{r} = \frac{n!}{r!\,(n-r)!}$. Permutations: $P(n,r) = \frac{n!}{(n-r)!}$.

How many ways can you choose $r$ items from $n$ types with repetition allowed (combinations with repetition)?

$\binom{n+r-1}{r}$.

State the Pigeonhole Principle in its generalized form.

If $n$ objects are placed into $k$ boxes, then at least one box contains at least $\left\lceil \frac{n}{k} \right\rceil$ objects.

State the Binomial Theorem.

$(x+y)^{n} = \sum_{k=0}^{n} \binom{n}{k} x^{n-k} y^{k}$.

Solve the homogeneous linear recurrence $a_n = 5a_{n-1} - 6a_{n-2}$ using its characteristic equation.

Characteristic equation: $r^{2} - 5r + 6 = 0$, roots $r=2,3$. General solution: $a_n = A\cdot 2^{n} + B\cdot 3^{n}$.

For a linear homogeneous recurrence with a repeated characteristic root $r$ of multiplicity $2$, what form does the solution take?

$a_n = (A + Bn)\, r^{n}$.

What is the ordinary generating function for the sequence $a_n = 1$ for all $n \geq 0$?

$\sum_{n=0}^{\infty} x^{n} = \frac{1}{1-x}$, valid for $|x|<1$.

Give the generating function $\sum_{n=0}^{\infty} \binom{n+k}{k} x^{n}$.

$\frac{1}{(1-x)^{k+1}}$.

How do you find the closed form of a sequence from its generating function?

Express the generating function as a rational function, decompose into partial fractions, then expand each term as a known power series; the coefficient of $x^{n}$ gives $a_n$.

What does it mean for a square matrix to be singular, in terms of its determinant?

A matrix $A$ is singular (non-invertible) if and only if $\det(A) = 0$.

State the formula for the inverse of a non-singular matrix $A$ using its adjugate.

$A^{-1} = \frac{1}{\det(A)}\,\operatorname{adj}(A)$, valid when $\det(A) \neq 0$.

How does the determinant of a product behave, and what is $\det(A^{-1})$?

$\det(AB) = \det(A)\det(B)$, and $\det(A^{-1}) = \frac{1}{\det(A)}$.

For an $n\times n$ matrix, how do $\det(kA)$ and $\det(A^{T})$ relate to $\det(A)$?

$\det(kA) = k^{n}\det(A)$ and $\det(A^{T}) = \det(A)$.

According to the Rouché-Capelli theorem, when is a system $A\vec{x}=\vec{b}$ consistent, and when does it have a unique solution?

It is consistent iff $\operatorname{rank}(A) = \operatorname{rank}([A\,|\,\vec{b}])$. The solution is unique iff this common rank equals the number of unknowns $n$; otherwise there are infinitely many solutions.

For a homogeneous system $A\vec{x}=\vec{0}$, when does a non-trivial solution exist?

A non-trivial solution exists iff $\det(A)=0$, i.e. iff $\operatorname{rank}(A)$ is less than the number of unknowns.

Define eigenvalues and eigenvectors via the equation $A\vec{x} = \lambda \vec{x}$, and give the characteristic equation.

A non-zero vector $\vec{x}$ with $A\vec{x}=\lambda\vec{x}$ is an eigenvector with eigenvalue $\lambda$. Eigenvalues solve the characteristic equation $\det(A - \lambda I) = 0$.

How do the sum and product of all eigenvalues of a matrix $A$ relate to its trace and determinant?

$\sum \lambda_i = \operatorname{trace}(A)$ and $\prod \lambda_i = \det(A)$.

What are the eigenvalues of a triangular matrix, and what is the eigenvalue property of a real symmetric matrix?

The eigenvalues of a triangular (or diagonal) matrix are its diagonal entries. A real symmetric matrix has all real eigenvalues and mutually orthogonal eigenvectors.

State the Cayley-Hamilton theorem.

Every square matrix satisfies its own characteristic equation: if $p(\lambda)=\det(A-\lambda I)$, then $p(A)=0$.

What is LU decomposition, and what is its main computational use?

It factors a square matrix as $A = LU$, where $L$ is lower triangular and $U$ is upper triangular. It is used to solve $A\vec{x}=\vec{b}$ efficiently via forward substitution ($L\vec{y}=\vec{b}$) then back substitution ($U\vec{x}=\vec{y}$), especially for multiple right-hand sides.

State the formal $\epsilon$-$\delta$ definition of $\lim_{x\to a} f(x) = L$.

For every $\epsilon > 0$ there exists $\delta > 0$ such that $0 < |x-a| < \delta$ implies $|f(x)-L| < \epsilon$.

State L'Hôpital's rule for evaluating an indeterminate limit of the form $\frac{0}{0}$ or $\frac{\infty}{\infty}$.

If $\lim_{x\to a}\frac{f(x)}{g(x)}$ is of form $\frac{0}{0}$ or $\frac{\infty}{\infty}$, then it equals $\lim_{x\to a}\frac{f'(x)}{g'(x)}$, provided the latter limit exists.

State the condition for a function $f$ to be continuous at a point $x=a$.

$f$ is continuous at $a$ if $f(a)$ is defined, $\lim_{x\to a} f(x)$ exists, and $\lim_{x\to a} f(x) = f(a)$.

What is the relationship between differentiability and continuity of a function at a point?

Differentiability at a point implies continuity at that point, but continuity does not imply differentiability (e.g. $f(x)=|x|$ at $x=0$).

State the first-derivative test and second-derivative test for a local extremum at a critical point $x=c$ where $f'(c)=0$.

First-derivative test: if $f'$ changes from $+$ to $-$ at $c$, it is a local maximum; from $-$ to $+$, a local minimum. Second-derivative test: $f''(c)<0 \Rightarrow$ local maximum, $f''(c)>0 \Rightarrow$ local minimum; $f''(c)=0$ is inconclusive.