Practice Question

Duration: 4 min

This video lesson is available to enrolled students.

Return to /learn/COAL-INDIA-MANAGEMENT-TRAINEE/engineering-maths/graph-theory/graph-isomorphism-definition-detection-and-problem-solving/asset-practice-question-19631 after enrolling

Inside: a video lesson and guided study material.

Module outline

  1. About Course: About the Course
  2. Paper-2 | Programming & Data Structures: C Fundamentals, Control Flow, Functions, Arrays & Pointers, Storage Classes, Structures & Enums, DMA, Macros, Scoping & File Handling, Introduction to DS, Array, Stack, Queue, Linked List, Tree, Graphs, Hashing
  3. Paper-2 | Databases / DBMS & SQL: Basics of DBMS, ER Diagram, Relational Model & Functional Dependencies, Keys & Integrity Constraints, Normalization (1NF - BCNF), Decomposition Properties & 4NF, File Organization & Indexing, Relational Algebra, SQL, Relational Calculus, Transaction Management, Concurrency Control
  4. Paper-2 | Algorithms: Algorithm Analysis, Time Complexity Analysis, Sorting Algorithms, Greedy Algorithms, Dynamic Programming, Minimum Spanning Trees, Shortest Path Algos
  5. Paper-2 | Computer Networks & Security: Introduction to CN, Data Communication, DLL: Access Control, DLL: Flow Control, DLL: Error Control, DLL: Framing, Data Link Layer - Ethernet, Net Layer: IPv4 & Proto, Net Layer: IP Addressing, Net Layer:Routing Protocol, Transport Layer Services, TL: Congestion & UDP, Application Layer, Hardware Basics, Network Access Technologies, Network Security
  6. Paper-2 | Digital Logic: Digital Systems & Boolean Basics, Logic Gates & Hardware, Boolean Expression, Boolean Minimization, Combinational Circuit, Sequential Circuits, Number System, Number Representation, Floating Point Rep
  7. Paper-2 | Operating System: Introduction to OS, Process Management, CPU Scheduling, Process Synchronization, Threads & Process Creation, Deadlock, Memory Management, Virtual Memory, Disc Scheduling, File Management
  8. Paper-2 | Theory of Computation: Introduction to TOC, Deterministic FA (DFA), Non-Deterministic FA, Regular Expressions, Grammar, Regular Language Properties, Moore & Mealy Machines, Pushdown Automata & CFG, Turing Machines
  9. Paper-2 | Computer Organization & Architecture: Basics of COA, Cache Memory Organization, Input Output Organisation, Pipelining, Instr Formats & Modes, Control Unit Design, Programming the Basic Computer
  10. Paper-2 | Compiler Design: Intro to Compilers, Lexical Analysis, Grammar & CFG, Syntax Analysis: Top-Down, Syntax Analysis: Bottom-Up, Semantic Analysis & SDT, Intermediate Code Gen, Code Optimization, Run Time Environment
  11. Paper-1 | General Awareness: Polity, Physics, Biology, Chemistry, Static General Knowledge, GK- Current Affairs, History, Geography, Indian Economy, Environment
  12. Paper-1 | Logical Reasoning: Series (Number and Letter Series) (Numerical Relations and Reasoning), Coding Decoding, Non Verbal Reasoning (Spatial Aptitude) (Spatial Reasoning) (Visual Reasoning), Data Interpretation, Blood Relations, Syllogisms, Deductive and Inductive Reasoning (Logical Deduction and Induction) (Prepositional Reasoning), Selection Decision Table (Decision Making), Clock, Calendar, Cubes & Dices, Directions (Direction Test), Analogy, Seating Arrangements, Analytical Reasoning (Counting Figures Reasoning)
  13. Paper-1 | Quantitative Aptitude: Ratio and Proportion (Ratios), Mixture and Alligation, Permutation and Combination, Number System, HCF LCM, Speed Time and Distance, Average, Age Problems, Percentage, Profit and Loss, Time and Work, Pipe and Cistern, Simple Interest and Compound Interest, Powers and Exponents (Surds and Indices), Mensuration and Geometry, Probability, Statistics, Arithmetic, Algebra
  14. Paper-1 | English: Vocabulary, Comprehension / Reading Comprehension / Unseen Passages (Critical Reasoning) (Paragraph Questions), Sentence Re-arrangements (Para Jumbles) (Narrative Sequencing), Sentence Correction (Error Correction), Sentence Completion (Fill in the blanks), Sentence Construction, Cloze Test (Cloze Passage)
  15. Coal India Previous Year Paper:
  16. Engineering Mathematics: Set Theory, Relations, Functions, Graph Theory, Group Theory, Propositional and Predicate Logic, Linear Algebra, Calculus
  17. Coal India Mock Test:
AI summary & chapters

AI Summary

An AI-generated summary of this video lecture.

This educational video segment focuses on solving graph theory problems involving simple non-isomorphic regular graphs. The instructor begins by presenting a problem requiring the identification of all possible configurations for 6 vertices and 6 edges where every vertex maintains an identical degree. The core constraint is that the graph must be regular, meaning each vertex connects to the same number of edges. The instructor systematically explores solutions by visualizing cycle graphs and disjoint unions, ensuring the total vertex count and edge count match the problem statement while maintaining regularity.

Chapters

  1. 0:00 – 2:00 00:00-02:00

    The video opens with the instructor displaying a practice question on screen asking for the number of simple non-isomorphic graphs possible with 6 vertices and 6 edges where every vertex has the same degree. Key constraints highlighted include 'simple', 'non-isomorphic', and the requirement for a regular graph structure. The instructor begins visualizing solutions by drawing a hexagonal cycle graph labeled C6, which satisfies the condition of 6 vertices and 6 edges with a degree of 2 for each vertex. Subsequently, the instructor draws two separate triangles (K3 + K3) to illustrate a second valid configuration where vertices also maintain a uniform degree of 2. These drawings are labeled G1 and G2 on the whiteboard to distinguish between the connected cycle graph and the disconnected union of cycles.

  2. 2:00 – 4:14 02:00-04:14

    The problem statement shifts to a new scenario involving 8 vertices and 8 edges with the same regularity constraint. The instructor draws a large octagon representing a single cycle graph C8, which serves as the first solution. Next, two disjoint squares are drawn and labeled C4 - C4 to demonstrate a configuration where the total vertex count is 8 and edges are distributed equally. The instructor then explores further combinations by drawing a house-shaped graph (a pentagon C5) alongside a separate triangle (C3), indicating that the sum of vertices and edges must equal 8. The final visual evidence shows three distinct configurations drawn in red ink: a single 8-cycle (C8), two disjoint 4-cycles (2C4), and a combination of a 5-cycle and a 3-cycle (C5 + C3). These drawings represent the complete set of non-isomorphic regular graphs satisfying the 8-vertex, 8-edge constraint.

The lecture demonstrates a methodical approach to enumerating regular graphs by decomposing the total number of vertices and edges into disjoint cycles. For a graph with n vertices and n edges where every vertex has degree 2, the solution space consists of all partitions of n into cycle lengths. The instructor uses visual aids to show that a single connected component (C6 or C8) is one solution, while disconnected components formed by combining smaller cycles (like two triangles for n=6 or a pentagon and triangle for n=8) are other valid solutions. This technique highlights the importance of checking both connectivity and degree constraints when determining non-isomorphic graph counts.

Loading lesson…