Discrete Mathematics: Graph Theory

Syllabus: Connectivity, Matching, Coloring.

Mark Distribution in Previous GATE

Welcome to the Graph Theory chapter, a cornerstone of Discrete Mathematics and a frequently tested area in the GATE Computer Science examination. Graph Theory provides a powerful framework for modeling relationships and processes across various domains, from social networks and transportation systems to computer networks and algorithm design. For GATE CS, this subject typically carries a weightage of 5-8 marks , often integrated with Data Structures and Algorithms. Questions range from direct application of definitions and formulas, analysis of graph properties, tracing graph algorithms, to problem-solving scenarios involving connectivity, coloring, and planarity. A strong grasp of graph theory fundamentals is crucial not only for scoring well but also for understanding advanced topics in computer science.

Topic-wise Key Concepts

Counting

Counting in graph theory involves determining the number of possible graphs, paths, cycles, or specific structures within graphs. It often relies on fundamental combinatorial principles.

• Definition and Core Idea: This topic focuses on enumerating different types of graphs or substructures within them, using principles of permutations, combinations, and other combinatorial techniques. It's about understanding how many ways a graph can be formed or how many specific patterns exist.

Important Formulas, Theorems, and Results:

• 1. Number of simple labeled graphs with $n$ vertices:

$2^{\binom{n}{2}} = 2^{n(n-1)/2}$

This is because for each pair of $n$ vertices, there can either be an edge or not.

• 2. Number of simple directed labeled graphs with $n$ vertices:

$2^{n(n-1)}$

For each ordered pair of distinct vertices $(u, v)$, there can be an edge from $u$ to $v$, or not.

• 3. Number of spanning trees in a complete graph $K_n$ (Cayley's Formula):

$n^{n-2}$

This formula is critical for counting trees on a given set of labeled vertices.

• 4. Number of spanning trees in a general graph (Matrix Tree Theorem): This theorem uses the Laplacian matrix of a graph, but its direct application is usually beyond GATE scope; Cayley's formula is more common.
• 5. Number of paths of length $k$ between two vertices in an adjacency matrix: The $(i, j)$-th entry of $A^k$ (where $A$ is the adjacency matrix) gives the number of paths of length $k$ from vertex $i$ to vertex $j$.

Key Properties and Identities:

• Understanding the difference between labeled and unlabeled graphs is crucial. GATE questions usually imply labeled graphs unless specified.

• Basic combinatorial identities like $\binom{n}{k} = \frac{n!}{k!(n-k)!}$ and $P(n, k) = \frac{n!}{(n-k)!}$ are fundamental.

• The Inclusion-Exclusion Principle can be used for more complex counting problems, especially when dealing with properties that overlap.

Common Pitfalls or Tricky Points:

• Overcounting or Undercounting: Ensure each distinct configuration is counted exactly once.

• Distinguishing Labeled vs. Unlabeled: Most GATE questions assume labeled vertices unless stated otherwise, which simplifies counting. Unlabeled graph counting is significantly harder.

• Specific Graph Types: Be careful when counting paths/cycles in specific graph types like trees, complete graphs, or bipartite graphs.

Standard Problem-Solving Techniques or Shortcuts:

• Direct Application of Formulas: For simple graphs, complete graphs, and spanning trees, direct formula application is common.
• Combinatorial Arguments: Break down the problem into smaller, manageable choices and multiply/add the possibilities.
• Recurrence Relations: For counting paths or specific structures, sometimes a recurrence relation can be formulated and solved.

Degree of Graph

The degree of a vertex is a fundamental property that quantifies its connectivity within a graph. It's essential for understanding graph structure and validating basic graph properties.

• Definition and Core Idea: The degree of a vertex $v$, denoted $\deg(v)$ or $d(v)$, is the number of edges incident to it. For directed graphs, we distinguish between in-degree (edges pointing to $v$) and out-degree (edges pointing from $v$).

Important Formulas, Theorems, and Results:

• 1. Handshaking Lemma (for undirected graphs): The sum of the degrees of all vertices in any undirected graph is equal to twice the number of edges.

$\sum_{v \in V} \deg(v) = 2|E|$

This is a cornerstone theorem in graph theory.

• 2. For directed graphs: The sum of in-degrees equals the sum of out-degrees, and both are equal to the total number of edges.

$\sum_{v \in V} \text{in-deg}(v) = \sum_{v \in V} \text{out-deg}(v) = |E|$

• 3. Number of odd-degree vertices: In any undirected graph, the number of vertices with odd degree must be even. This is a direct consequence of the Handshaking Lemma.
• 4. Maximum degree $\Delta(G)$ and Minimum degree $\delta(G)$: These denote the maximum and minimum degrees among all vertices in graph $G$, respectively.

Key Properties and Identities:

• The Handshaking Lemma is a powerful tool for checking the validity of a degree sequence or finding the number of edges.
• A graph cannot exist if its degree sequence violates the Handshaking Lemma or has an odd number of odd-degree vertices.
• For a simple graph with $n$ vertices, the maximum degree of any vertex is $n - 1$.

Common Pitfalls or Tricky Points:

• Self-loops: In some contexts, a self-loop at a vertex contributes 2 to its degree. GATE questions usually specify if self-loops are allowed or assume simple graphs (no self-loops, no multiple edges).
• Multiple Edges: If multiple edges are allowed between two vertices, each edge contributes to the degree.
• Directed vs. Undirected: Always be clear whether the graph is directed or undirected when calculating degrees.

Standard Problem-Solving Techniques or Shortcuts:

• Direct Application of Handshaking Lemma: Often used to find the number of edges given a degree sequence, or to determine if a given degree sequence is possible.
• Parity Check: Quickly identify impossible degree sequences by checking the number of odd-degree vertices.

Graph Algorithms

Graph algorithms are systematic procedures for solving problems on graphs, such as finding paths, spanning trees, or optimal routes. They are central to computer science applications.

• Definition and Core Idea: These are algorithms designed to traverse, search, analyze, and optimize properties of graphs. They form the backbone of many real-world applications, from network routing to social network analysis.

Important Algorithms, Formulas, and Complexities:

• 1. Breadth-First Search (BFS): Explores a graph layer by layer.

• ▪ Purpose: Find shortest path in unweighted graphs, find connected components.

• ▪ Time Complexity: $O(V + E)$ for adjacency list, $O(V^2)$ for adjacency matrix.

• 2. Depth-First Search (DFS): Explores as far as possible along each branch before backtracking.

• ▪ Purpose: Find connected components, topological sort, detect cycles, find bridges/articulation points.

• ▪ Time Complexity: $O(V + E)$ for adjacency list, $O(V^2)$ for adjacency matrix.

• 3. Dijkstra's Algorithm: Finds the shortest paths from a single source vertex to all other vertices in a graph with non-negative edge weights.

• ▪ Purpose: Single-source shortest path.

• ▪ Time Complexity: $O(E \log V)$ with a Fibonacci heap, $O(E + V \log V)$ with a binary heap, $O(V^2)$ with adjacency matrix.

• 4. Prim's Algorithm: Finds a Minimum Spanning Tree (MST) in a weighted, undirected graph.

• ▪ Purpose: MST.

• ▪ Time Complexity: $O(E \log V)$ with a binary heap, $O(V^2)$ with adjacency matrix.

• 5. Kruskal's Algorithm: Finds a Minimum Spanning Tree (MST) in a weighted, undirected graph.

• ▪ Purpose: MST.

• ▪ Time Complexity: $O(E \log E)$ or $O(E \log V)$ using a Disjoint Set Union (DSU) data structure.

• 6. Bellman-Ford Algorithm: Finds the shortest paths from a single source vertex to all other vertices, even with negative edge weights. Detects negative cycles.

• ▪ Purpose: Single-source shortest path with negative weights.

• ▪ Time Complexity: $O(VE)$.

• 7. Floyd-Warshall Algorithm: Finds all-pairs shortest paths in a weighted graph, can handle negative weights but not negative cycles.

• ▪ Purpose: All-pairs shortest path.

• ▪ Time Complexity: $O(V^3)$.

• 8. Topological Sort: Linear ordering of vertices such that for every directed edge $(u, v)$, $u$ comes before $v$. Applicable only to Directed Acyclic Graphs (DAGs).

• ▪ Purpose: Ordering tasks with dependencies.

• ▪ Time Complexity: $O(V + E)$ (using DFS or Kahn's algorithm).

• 9. Ford-Fulkerson Algorithm (and Edmonds-Karp): Finds the maximum flow in a flow network.

• ▪ Purpose: Maximum flow.

• ▪ Time Complexity: Ford-Fulkerson is not polynomial in general; Edmonds-Karp is $O(VE^2)$.

Key Properties and Identities:

• Greedy Algorithms: Prim's, Kruskal's, Dijkstra's are greedy algorithms that make locally optimal choices.

• Dynamic Programming: Floyd-Warshall and Bellman-Ford use dynamic programming principles.

• Connectivity: BFS/DFS can determine if a graph is connected or find its connected components.

• Cycles: DFS can detect cycles in both directed and undirected graphs.

Common Pitfalls or Tricky Points:

• Negative Edge Weights: Dijkstra's fails with negative edge weights; use Bellman-Ford or Floyd-Warshall.

• Disconnected Graphs: Algorithms like Dijkstra's might not reach all vertices if the graph is disconnected from the source.

• Choosing the Right Algorithm: Understand the constraints (weighted/unweighted, directed/undirected, negative weights, single-source/all-pairs) to select the appropriate algorithm.

• Adjacency List vs. Matrix: Be aware of how the graph representation affects time complexity.

Standard Problem-Solving Techniques or Shortcuts:

• Tracing: Practice tracing algorithms step-by-step on small graphs to understand their mechanics.

• Recognizing Patterns: Identify if a problem can be mapped to a standard graph algorithm (e.g., "minimum cost to connect all cities" suggests MST).

• Complexity Analysis: Be able to derive or recall the time and space complexity for common algorithms.

Graph Coloring

Graph coloring assigns labels (colors) to graph elements subject to certain constraints, often used to model scheduling or resource allocation problems.

• Definition and Core Idea: Vertex coloring assigns a color to each vertex such that no two adjacent vertices have the same color. The minimum number of colors required for a graph $G$ is called its chromatic number, denoted $\chi(G)$.

Important Formulas, Theorems, and Results:

• 1. Chromatic Number $\chi(G)$: The smallest integer $k$ such that $G$ is $k$-colorable.
• 2. Lower Bound: For any graph $G$, $\chi(G) \geq \omega(G)$, where $\omega(G)$ is the clique number (size of the largest clique).
• 3. Upper Bound (Brooks' Theorem): For a connected graph $G$ that is neither a complete graph nor an odd cycle, $\chi(G) \leq \Delta(G)$, where $\Delta(G)$ is the maximum degree. In general, $\chi(G) \leq \Delta(G) + 1$.
• 4. Bipartite Graphs: A graph is bipartite if and only if it contains no odd-length cycles. If a graph is bipartite and has at least one edge, then $\chi(G) = 2$.
• 5. Planar Graphs (Four Color Theorem): Every planar graph is 4-colorable. Thus, for any planar graph $G$, $\chi(G) \leq 4$.
• 6. Chromatic Polynomial $P(G, k)$: A polynomial whose value at integer $k$ is the number of ways to color $G$ using at most $k$ colors. For a graph with $n$ vertices, $P(G, k)$ is a polynomial in $k$ of degree $n$.

Key Properties and Identities:

• A graph is 2-colorable if and only if it is bipartite.

• If a graph contains a clique of size $k$, then at least $k$ colors are needed.

• The chromatic number of a complete graph $K_n$ is $n$.

• The chromatic number of a cycle graph $C_n$ is 2 if $n$ is even, and 3 if $n$ is odd.

Common Pitfalls or Tricky Points:

• Minimum vs. Any Coloring: The goal is to find the minimum number of colors, not just any valid coloring.

• Identifying Cliques: Finding the largest clique ($\omega(G)$) can be hard, but it provides a lower bound for $\chi(G)$.

• Edge Coloring ($\chi'(G)$): Similar concept but for edges (adjacent edges have different colors). Vizing's Theorem states $\Delta(G) \leq \chi'(G) \leq \Delta(G) + 1$. GATE usually focuses on vertex coloring.

Standard Problem-Solving Techniques or Shortcuts:

• Greedy Coloring: Assign colors iteratively to vertices in some order (e.g., decreasing degree). While not always optimal, it's a common heuristic.

• Identify Cliques and Odd Cycles: These structures directly give lower bounds for the chromatic number.

• Trial and Error/Backtracking: For small graphs, try to color with 2, then 3, etc., until a valid coloring is found.

Graph Connectivity

Graph connectivity measures how robust a graph is to the removal of vertices or edges. It's crucial for network reliability and fault tolerance.

• Definition and Core Idea: Connectivity refers to the property of a graph being "connected," meaning there's a path between any two vertices. More generally, it quantifies how many vertices or edges must be removed to disconnect the graph.

Important Formulas, Theorems, and Results:

• 1. Connected Graph: A graph is connected if there is a path between every pair of distinct vertices.
• 2. Connected Components: Maximal connected subgraphs.
• 3. Cut Vertex (Articulation Point): A vertex whose removal increases the number of connected components.
• 4. Cut Edge (Bridge): An edge whose removal increases the number of connected components.
• 5. Vertex Connectivity $\kappa(G)$: The minimum number of vertices whose removal disconnects $G$ or reduces it to a trivial graph. A graph is $k$-connected if $\kappa(G) \geq k$.
• 6. Edge Connectivity $\lambda(G)$: The minimum number of edges whose removal disconnects $G$. A graph is $k$-edge-connected if $\lambda(G) \geq k$.
• 7. Relationship: For any graph $G$, $\kappa(G) \leq \lambda(G) \leq \delta(G)$, where $\delta(G)$ is the minimum degree of $G$.
• 8. Menger's Theorem: For any two non-adjacent vertices $u$ and $v$ in a graph $G$, the maximum number of vertex-disjoint paths between $u$ and $v$ is equal to the minimum number of vertices whose removal separates $u$ and $v$. (Similar theorem for edge-disjoint paths and edge cuts).

Key Properties and Identities:

• A tree with more than one vertex has $\kappa(G) = 1$ and $\\$lambda(G) = 1$.

• A complete graph $K_n$ has $\kappa(K_n) = n - 1$ and $\\$lambda(K_n) = n - 1$.

• If a graph has a bridge, its edge connectivity is 1. If it has an articulation point, its vertex connectivity is 1 (unless it's $K_2$).

Common Pitfalls or Tricky Points:

• Trivial Graph: For a complete graph $K_n$, removing $n - 1$ vertices disconnects it into a trivial graph (single vertex), so $\kappa(K_n) = n - 1$.

• Distinguishing Vertex vs. Edge Connectivity: Carefully read whether the question asks for vertex or edge removal.

• Disconnected Graphs: For a disconnected graph, $\kappa(G) = 0$ and $\\$lambda(G) = 0$.

Standard Problem-Solving Techniques or Shortcuts:

• BFS/DFS: Can be used to find connected components, bridges, and articulation points.

• Trial and Error: For small graphs, try removing vertices/edges to find the minimum set that disconnects the graph.

• Apply $\kappa(G) \leq \lambda(G) \leq \delta(G)$: This inequality provides quick bounds.

Graph Isomorphism

Graph isomorphism determines if two graphs are structurally identical, regardless of their vertex labeling or drawing style. It's a fundamental concept for comparing graphs.

• Definition and Core Idea: Two graphs $G_1 = (V_1, E_1)$ and $G_2 = (V_2, E_2)$ are isomorphic if there exists a bijective function $f : V_1 \rightarrow V_2$ such that for any pair of vertices $u, v \in V_1$, $\{u, v\} \in E_1$ if and only if $\{f(u), f(v)\} \in E_2$. Essentially, they have the same structure.
• Important Properties (Invariants):
• 1. Number of Vertices: $|V_1| = |V_2|$.
• 2. Number of Edges: $|E_1| = |E_2|$.
• 3. Degree Sequence: Both graphs must have the same degree sequence (multiset of degrees).
• 4. Number of Connected Components: Must be the same.
• 5. Cycle Lengths: The number of cycles of each specific length must be the same.
• 6. Connectivity: Same vertex and edge connectivity.
• 7. Chromatic Number: Must be the same.
• 8. Presence of Subgraphs: If $G_1$ contains a subgraph $H$, then $G_2$ must also contain $H$.
• Key Properties and Identities:
• If any of the invariants differ, the graphs are definitely NOT isomorphic.
• If all invariants are the same, the graphs MIGHT be isomorphic, but it's not a guarantee (e.g., regular graphs can have the same degree sequence but be non-isomorphic).
• The Graph Isomorphism Problem (determining if two graphs are isomorphic) is in NP, but its exact complexity class is unknown (neither P nor NP-complete is proven). For GATE, problems are usually small enough to solve by inspection or invariant checking.
• Common Pitfalls or Tricky Points:
• Proving Non-Isomorphism: This is generally easier; just find one invariant that differs.
• Proving Isomorphism: This requires finding an explicit bijective mapping $f$, which can be challenging. Often, it involves matching vertices with identical properties (e.g., same degree, same neighborhood structure).
• Visual Deception: Graphs drawn differently can be isomorphic, and graphs drawn similarly can be non-isomorphic.
• Standard Problem-Solving Techniques or Shortcuts:
• Check Invariants Systematically: Start with simple invariants like number of vertices, edges, and degree sequence. If any differ, stop.
• Match Vertices by Properties: Look for unique vertices (e.g., a vertex with degree 1, or a vertex part of a unique cycle structure) and try to map them.
• Adjacency Matrix Comparison: If two graphs are isomorphic, their adjacency matrices can be made identical by permuting rows and columns. This is computationally intensive for humans but conceptually useful.

Graph Matching

Graph matching is about finding a set of edges that do not share any common vertices, often used in assignment problems or resource allocation.

• Definition and Core Idea: A matching $M$ in a graph $G$ is a set of edges such that no two edges in $M$ share a common vertex. A vertex is matched (or covered) if it is an endpoint of an edge in $M$; otherwise, it is unmatched .
• Important Formulas, Theorems, and Results:
• 1. Maximum Matching: A matching with the largest possible number of edges.
• 2. Perfect Matching: A matching that covers all vertices of the graph. A perfect matching can only exist if $|V|$ is even.
• 3. Augmenting Path: A path that starts and ends at unmatched vertices, and whose edges alternate between being in the current matching and not in the current matching. An augmenting path can be used to increase the size of a matching.
• 4. Hall's Marriage Theorem (for Bipartite Graphs): A bipartite graph $G = (U \cup V, E)$ has a matching that covers all vertices in $U$ if and only if for every subset $A \subseteq U$, $|N(A)| \geq |A|$, where $N(A)$ is the set of neighbors of vertices in $A$.
• 5. Tutte's Theorem (for General Graphs): A graph $G$ has a perfect matching if and only if for every subset $S \subseteq V$, the number of odd components in $G - S$ is less than or equal to $|S|$. (This is more complex and less common in GATE than Hall's).
• Key Properties and Identities:
• The size of a maximum matching in a bipartite graph can be found using network flow algorithms (e.g., by converting to a max-flow problem).
• Every perfect matching is a maximum matching, but not vice-versa.
• A graph can have multiple maximum matchings.

Common Pitfalls or Tricky Points:

• Confusing Matching with Vertex Cover or Edge Cover: These are related but distinct concepts. A vertex cover is a set of vertices that touch all edges. An edge cover is a set of edges that touch all vertices (only exists if no isolated vertices).
• General vs. Bipartite Graphs: Finding maximum matchings in general graphs is more complex (e.g., Edmonds' blossom algorithm) than in bipartite graphs. GATE usually focuses on bipartite matching or simpler cases.
• Existence of Perfect Matching: A perfect matching requires an even number of vertices.

Standard Problem-Solving Techniques or Shortcuts:

• Greedy Approach: While not always optimal for maximum matching, a greedy approach (e.g., pick an edge, remove its endpoints, repeat) can give a good starting point.
• Augmenting Paths: For bipartite graphs, the concept of augmenting paths is key. Start with an empty matching, find an augmenting path, update the matching, and repeat until no more augmenting paths exist. This is the basis of the Hopcroft-Karp algorithm.
• Applying Hall's Theorem: For bipartite graphs, use Hall's condition to check for the existence of a matching covering one side.

Graph Planarity

Graph planarity deals with whether a graph can be drawn on a plane without any edges crossing. It has applications in circuit design and network visualization.

• Definition and Core Idea: A graph is planar if it can be drawn in the plane without any edges crossing each other (except at vertices). Such a drawing is called a planar embedding.

Important Formulas, Theorems, and Results:

• 1. Euler's Formula for Planar Graphs: For any connected planar graph with $V$ vertices, $E$ edges, and $F$ faces (regions),

$V - E + F = 2$

This formula is fundamental for planar graphs.

• 2. Corollaries of Euler's Formula (for simple connected planar graphs with $V \geq 3$):

• ▪ If $G$ has no cycles of length 3 (i.e., no $K_3$ subgraph), then $E \leq 2V - 4$.

• ▪ In general, $E \leq 3V - 6$.

• ▪ There is at least one vertex with degree at most 5 ($\delta(G) \leq 5$).

• 3. Kuratowski's Theorem: A graph is planar if and only if it does not contain a subgraph that is a subdivision of $K_5$ (complete graph on 5 vertices) or $K_{3,3}$ (complete bipartite graph with 3 vertices in each partition).

• ▪ A subdivision of a graph is obtained by replacing edges with paths.

Key Properties and Identities:

• $K_5$ and $K_{3,3}$ are non-planar.
• Any graph that contains $K_5$ or $K_{3,3}$ as a minor (or subdivision) is non-planar.
• The dual of a planar graph is also planar.

Common Pitfalls or Tricky Points:

• Misapplying Euler's Formula: Remember it's for connected planar graphs. For disconnected graphs, $V - E + F = 1 + k$, where $k$ is the number of connected components.
• Identifying Subdivisions: Recognizing $K_5$ or $K_{3,3}$ subdivisions can be tricky. Look for 5 vertices all connected to each other (possibly via paths) or 6 vertices arranged in a bipartite manner.
• Different Drawings: A graph might look non-planar in one drawing but be planar in another. The definition requires existence of a planar drawing.

Standard Problem-Solving Techniques or Shortcuts:

• Check Euler's Formula Corollaries: If $E > 3V - 6$ (or $E > 2V - 4$ if no triangles), the graph is definitely non-planar. This is a quick check for non-planarity.
• Look for $K_5$ or $K_{3,3}$ Subdivisions: Try to simplify the graph by removing degree-2 vertices (which don't affect planarity for Kuratowski's theorem) or identifying dense subgraphs.
• Redrawing: For small graphs, try to redraw them to eliminate crossings.

Jaccard Coefficient

The Jaccard Coefficient is a statistical measure used to gauge the similarity between two sets, finding applications in data mining, machine learning, and graph analysis (e.g., comparing neighbor sets).

• Definition and Core Idea: The Jaccard Coefficient (or Jaccard Index) measures the similarity between two finite

sets, $A$ and $B$, as the size of their intersection divided by the size of their union. It quantifies the overlap between the sets.

Important Formulas, Theorems, and Results:

1. Jaccard Coefficient $J(A, B)$:

$J(A, B) = \frac{|A \cap B|}{|A \cup B|}$

2. Jaccard Distance $D_J(A, B)$: Measures dissimilarity.

$D_J(A, B) = 1 - J(A, B) = \frac{|A \cup B| - |A \cap B|}{|A \cup B|}$

Key Properties and Identities:

• The Jaccard Coefficient ranges from 0 to 1.

• ▪ $J(A, B) = 1$ if $A = B$ (perfect similarity).

• ▪ $J(A, B) = 0$ if $A \cap B = \emptyset$ (no similarity).

• It is symmetric: $J(A, B) = J(B, A)$.

• It is sensitive to the size of the union; a large union with a small intersection leads to a low coefficient.

Common Pitfalls or Tricky Points:

• Miscalculating Intersection or Union: Ensure correct set operations, especially when dealing with lists that might contain duplicates (convert to sets first).

• Empty Sets: If both sets are empty, the Jaccard coefficient is usually defined as 1 (perfect similarity). If one is empty and the other is not, it's 0.

• Application Context: In graph theory, it's often used to compare the neighborhood sets of two vertices to determine their "structural similarity" or to compare sets of features associated with graph nodes.

Standard Problem-Solving Techniques or Shortcuts:

• Direct Calculation: Identify the elements in the intersection and union, then apply the formula.

• Venn Diagrams: For small sets, a Venn diagram can help visualize the intersection and union.

Quick Formula Reference

• Counting Simple Labeled Graphs ($n$ vertices): $2^{\binom{n}{2}}$

• Counting Simple Directed Labeled Graphs ($n$ vertices): $2^{n(n-1)}$

• Cayley's Formula (Spanning Trees in $K_n$): $n^{n-2}$

• Handshaking Lemma (Undirected): $\sum_{v \in V} \deg(v) = 2|E|$

• Handshaking Lemma (Directed): $\sum_{v \in V} \text{in-deg}(v) = \sum_{v \in V} \text{out-deg}(v) = |E|$

• BFS/DFS Time Complexity: $O(V + E)$ (adj list), $O(V^2)$ (adj matrix)

• Dijkstra's Time Complexity: $O(E \log V)$ (binary heap), $O(V^2)$ (adj matrix)

• Prim's/Kruskal's Time Complexity (MST): $O(E \log V)$ or $O(E \log E)$

• Bellman-Ford Time Complexity: $O(VE)$

• Floyd-Warshall Time Complexity: $O(V^3)$

• Topological Sort Time Complexity: $O(V + E)$

• Chromatic Number Lower Bound: $\chi(G) \geq \omega(G)$ (clique number)

• Chromatic Number Upper Bound (Brooks' Theorem): $\chi(G) \leq \Delta(G)$ (for non-complete, non-odd cycle connected graphs), else $\chi(G) \leq \Delta(G) + 1$

• Bipartite Graph Chromatic Number: $\chi(G) = 2$ (if connected and has edges)

• Planar Graph Chromatic Number (Four Color Theorem): $\chi(G) \leq 4$

• Connectivity Relationship: $\kappa(G) \leq \lambda(G) \leq \delta(G)$

• Euler's Formula (Connected Planar Graph): $V - E + F = 2$

• Planarity Condition (Simple Connected Planar, $V \geq 3$): $E \leq 3V - 6$

• Planarity Condition (Simple Connected Planar, no $K_3$, $V \geq 3$): $E \leq 2V - 4$

• Kuratowski's Theorem: Planar iff no $K_5$ or $K_{3,3}$ subdivision

• Jaccard Coefficient: $J(A, B) = \frac{|A \cap B|}{|A \cup B|}$

• Jaccard Distance: $D_J(A, B) = 1 - J(A, B)$

Important Tips for GATE

• 1. Master Definitions and Basic Properties: Many GATE questions test fundamental definitions (e.g., what is a bridge, what is a perfect matching) and direct consequences of theorems. Ensure you know what each term means precisely.
• 2. Practice Drawing and Visualizing Graphs: For problems involving planarity, isomorphism, or connectivity, sketching the graph and trying different layouts can be immensely helpful. Don't rely solely on abstract representations.
• 3. Understand Algorithm Mechanics and Complexity: Don't just memorize complexities; understand how BFS, DFS, Dijkstra's, Prim's, and Kruskal's work step-by-step. Be prepared to trace them on small examples and identify their time/space complexities for both adjacency list and matrix representations.
• 4. Pay Attention to Graph Types and Constraints: Is the graph directed or undirected? Weighted or unweighted? Simple or multi-graph? Does it allow self-loops? These details significantly impact which formulas or algorithms apply. For example, Dijkstra's fails with negative edge weights.
• 5. Use Invariants for Isomorphism: When checking for isomorphism, systematically compare invariants like number of vertices, edges, degree sequence, and cycle lengths. If any invariant differs, the graphs are not isomorphic. This is a powerful shortcut.
• 6. Be Wary of Common Pitfalls: Remember that Euler's formula applies to connected planar graphs. Dijkstra's doesn't work with negative weights. A greedy coloring isn't always optimal. Keep these exceptions in mind.
• 7. Time Management for Tracing Problems: For algorithm tracing questions, work carefully and systematically. Use scratch paper to keep track of visited nodes, distances, or parent pointers. Avoid rushing, as a single error can invalidate the entire trace.
• 8. Review Special Graph Types: Be familiar with properties of common graphs like complete graphs ($K_n$), complete bipartite graphs ($K_{m,n}$), cycle graphs ($C_n$), path graphs ($P_n$), and trees. Their specific properties often appear in questions.