Graph numbers | chromatic number of graphs | GATE 2023

📍 Telegram channel link(for NOTES and DOUBTS)
t.me/gatecsele...
📍I will cover entire 'GATE CS-IT' syllabus and make videos🎥 of each and every PYQ on youtube.
📍I am not taking even a single rupee💸 from any student👩🏻‍💻.
📍If you want to support me😀then you can donate💰any amount of money according to your wish🤞🏻.
📍UPI ID ⬇️
tinyurl.com/AK...
📚 Subject Wise Playlist 📚
📖 Pointers In C - • Pointers in C (from C ...
📖 DBMS -
• Databases (DBMS) for G...
📖 COMPUTER NETWORK (CN) -
• Computer Networks (CN)...
📖 DISCRETE MATHS -
• Discrete Mathematics f...
🔖Logic - • Logic (from Discrete M...
🔖 Combinatorics -
• Combinatorics (from Di...
🔖 Set Theory -
• Set Theory (from Discr...
🔖 Group Theory -
• Group Theory (from Dis...
🔖 Graph Theory -
• Graph Theory (from Dis...
🔖 Poset Lattice And Boolean Algebra -
• Poset Lattice and Bool...
🔖 Generating Function -
• Generating Functions (...
🔖 Discrete Probability -
• Discrete Probability (...
📖 TOC -
• Theory of Computation ...
📖 Digital Logic -
• Digital Logic for GATE...
📖 C Language -
• C Language for GATE - ...
📖 Aptitude -
• Aptitude for GATE - Co...
📋 PYQ and Solutions 📋
▶️ GATE 2020 CSE Solution -
• GATE CSE 2020 Solutions
▶️ DBMS Gate Questions -
• GATE PYQs | DBMS
▶️ CN Gate Questions -
• GATE PYQs | Computer N...
▶️ Logic Gate Questions -
• GATE PYQs | Logic
▶️ GATE 2021 SET 1 SOLUTIONS -
• GATE CSE 2021 Solutions
▶️ Combinatorics Gate Questions -
• GATE PYQs | Combinatorics
▶️ Set Theory Gate Questions -
• GATE PYQs | Set Theory
▶️ Group Theory Gate Questions -
• GATE PYQs | Group Theory
👩🏻‍🎓 TOPPERS PODCAST - • The GATE Toppers Podcast
📽️ General Videos -
• General Videos
gate cse,gate computer science,gate lectures,gate computer science lectures,amit sir,gatecse,computer science,cs,computer,air 1,top rank gate,best lectures for gate,complete lectures for gate,gate 2022,gate 2023,gate cse 2022,gate cse 2023,toc,dbms,combinatorics,discrete maths,group theory,gate cse lectures,gate cse preparation strategy,gate cse preparation
gate cse,gate computer science,gate lectures,gate computer science lectures,amit sir,gatecse,computer science,cs,computer,air 1,top rank gate,best lectures for gate,complete lectures for gate,gate 2022,gate 2023,gate cse 2022,gate cse 2023,gate cse lectures,gate cse preparation,gate cse preparation strategy,reasoning syllabus for gate,reasoning syllabus,reasoning,what is reasoning,syllabus of reasoning,free reasoning classes,reasoning gate cse

[@sahebsarkar8330]

at 13:04 max clique size 5 because a complete graph can be clique of it self.

[@zbeast7872]

42:07 just imagine how strong its intutive power posess by that mathematician WOW

[@Thakur_Abhays]

13:13 largest clique size why 4 ? given graph is itself complete graph then largest clique size is 5.

[@sprectza]

Clique cannot have it's own existence. It has to reside as a proper subgraph of a graph. Watch video names as "Subgraph | Induced subgraph | clique" sir has explained it very clearly.

[@Thakur_Abhays]

@@sprectza It is a clique of itself watch video no. 17 at 16:48 sir has given similar example that means in complete graph largest clique size is = order of a complete graph

[@sprectza]

@@Thakur_Abhays Yes you are right, there is a contradiction. Your question is legit. A clique is a induced subgraph so for complete graph maximal clique should be the graph itself. Good observation.

[@debarghamukherjee1440]

I think this has been overlooked by sir somehow. Largest clique size is 5 only

[@harshilshah8983]

There are 2 ways of thinking here. 1. Graph is also a subgraph of itself. So for Kn, clique will be Kn itself. Now largest clique is Kn (i.e size n) so kg >= n. And since there are maximum 'n' vertices, kg = n. 2. In Kn, Kn-1 will be present as largest subgraph. And if we consider Kn-1 as clique for Kn then kg>=(n-1) for Kn. And we know that kg for Kn is n & n>(n-1). Sir has explained using 2nd approach.

[@devkulsahu3430]

at 21:10, In the case of wheel graph: Chromatic No. = 4 (when n is even) and 3(when n is odd)

[@sprectza]

An interesting property of bi-partite graphs, if we take the complement of the complete bi-partite graph, the resultant graph would be a 2-component disconnected graph where each component is a complete graph. Can this idea be extended for complete k-partite graphs?

[@shariqfaraz]

@10:40 its mentioned "graph of size n" . Since size of a graph is no. of edges, so if we are considering no. of vertices and not edges, then in the therom it should be written "graph of order n" instead of "size n"

[@pratikpawar05]

great observation..I think it should be "order n".

[@keipetsympull1574]

to those who have watched your Logic playlist , this video is not more than 10 mins video.

[@sukhjeetiisc]

Sir at 18:21 graph is k5 hence kg is 5

[@237_subhojitroy9]

sir ye aapka probability k complete playlist h??