Channel Title: Sarada Herke Channel Description: This channel is created to provide free and easy access to graduate level topics in Mathematics, mostly focused on Combinatorics and Graph Theory. My name is Sarada Herke, I have a MSc. in Mathematics from the University of Victoria and a PhD from the University of Queensland, specializing in Graph Theory. <video> Graph Theory: 60. Non Planar Graphs Description: In this video we formally prove that the complete graph on 5 vertices is non-planar. Then we prove that a planar graph with no triangles has at most 2n-4 edges, where n is the number of vertices. Using this fact, we formally prove that the complete biparite graph with partite sets both of size 3 is non-planar. -- Bits of Graph Theory by Dr. Sarada Herke. Related videos: GT59 Maximal Planar Graphs - https://youtu.be/_d_6JvceAwE GT58 Euler's Formula for Plane Graphs - https://youtu.be/5ywif1Zpeo4 GT57 Planar Graphs - https://youtu.be/wnYtITkWAYA GT19 Graph is Bipartite iff No Odd Cycle - https://youtu.be/YiGFhWxtHjQ For quick videos about Math tips and useful facts, check out my other channel "Spoonful of Maths" - http://youtube.com/spoonfulofmaths Video Production by: Giuseppe Geracitano (goo.gl/O8TURb) </video> <video> Graph Theory: 62. Graph Minors and Wagner's Theorem Description: In this video, we begin with a visualisation of an edge contraction and discuss the fact that an edge contraction may be thought of as resulting in a multigraph or simple graph, depending on the application. We then state the definition a contraction of edge e in a graph G resulting in a simple graph G/e. Next we define graph minors and state Wagner's Theorem, which gives a characterisation of planar graphs. Finally, we compare Wagner's Theorem with Kuratowski's Theorem. -- Bits of Graph Theory by Dr. Sarada Herke. Related videos: Graph Theory: 61. Characterization of Planar Graphs - https://youtu.be/UkjJE3bmPV0 Graph Theory: 57. Planar Graphs - https://youtu.be/wnYtITkWAYA For quick videos about Math tips and useful facts, check out my other channel "Spoonful of Maths" - http://youtube.com/spoonfulofmaths Video Production by: Giuseppe Geracitano (goo.gl/O8TURb) </video> <video> Graph Theory: 64. Vertex Colouring Description: In this video we define a (proper) vertex colouring of a graph and the chromatic number of a graph. We discuss some basic facts about the chromatic number as well as how a k-colouring partitions the vertex set into k independent sets (check out video #50 for more about independent sets). -- Bits of Graph Theory by Dr. Sarada Herke. Related videos: https://youtu.be/71XbdtoG7P8 - Graph Theory: 04. Families of Graphs https://youtu.be/03PUwWef2Dg - Graph Theory: 50. Maximum vs Maximal For quick videos about Math tips and useful facts, check out my other channel "Spoonful of Maths" - http://youtube.com/spoonfulofmaths Video Production by: Giuseppe Geracitano (goo.gl/O8TURb) </video> <video> Graph Theory: 58. Euler's Formula for Plane Graphs Description: In a connected plane graph with n vertices, m edges and r regions, Euler's Formula says that n-m+r=2. In this video we try out a few examples and then prove this fact by induction. We discuss a generalization to disconnected plane graphs as well as what Euler's Formula means for a polyhedron. -- Bits of Graph Theory by Dr. Sarada Herke. Related videos: GT 57 Planar Graphs - https://youtu.be/wnYtITkWAYA GT 55 Bridges and Blocks - https://youtu.be/iGsxKUzW3cs For the proof that in a tree on n vertices, the number of edges is n-1, check out this video: GT 37: Which Graphs are Trees - https://youtu.be/BptJFixSseM For the proof that an edge is a bridge if and only if it lies on no cycle, check out this video: GT 34: Bridge edges - http://youtu.be/zxu0dL436gI For quick videos about Math tips and useful facts, check out my other channel "Spoonful of Maths" - http://youtube.com/spoonfulofmaths Video Production by: Giuseppe Geracitano (goo.gl/O8TURb) </video> <video> Graph Theory FAQs: 01. More General Graph Definition Description: In video 02: Definition of a Graph, we defined a (simple) graph as a set of vertices together with a set of edges where the edges are 2-subsets of the vertex set. Notice that this definition does not allow for multiple edges or loops. In general on this channel, we have been discussing only simple graphs (no multiple edges or loops), so this definition is perfect for our needs (and is used in many textbooks and papers). However, if we require more precision in our definition of a graph, say if we want to consider loops or multiple edges, there is a standard general definition that we should use. It defines a graph as a set of vertices V, a set of edges E, and a mapping f which maps every edge to a set of endpoints. In this video we look at an example graph defined in this way and discuss how multiple edges and loops can come about. -- Bits of Graph Theory by Dr. Sarada Herke. Related videos: GT 02: Definition of a Graph - https://youtu.be/S1Zwhz-MhCs GT 09: Graph Isomorphisms - https://youtu.be/yFpRpxOry-A For quick videos about Math tips and useful facts, check out my other channel "Spoonful of Maths" - http://youtube.com/spoonfulofmaths </video> <video> Graph Theory: 65. 2-Chromatic Graphs Description: In this video we begin by showing that the chromatic number of a tree is 2. Yet, if the chromatic number of a graph is 2, this does not imply that the graph is a tree. We then prove that the chromatic number of a graph is 2 if and only if the graph is bipartite. -- Bits of Graph Theory by Dr. Sarada Herke. Related videos: https://youtu.be/RatkBWHUSqo - FAQs: 04. Isomorphism vs Homomorphism https://youtu.be/YiGFhWxtHjQ - GT: 19. Graph is Bipartite iff No Odd Cycle </video> <video> Sarada's Favourite Science Hero - The Laborastory 2015 Description: This is the talk I gave for "The Laborastory" series about science stories and great science heroes. The hero I chose to talk about is Sal Khan, the creator of Khan Academy and the educator that has revolutionised on-line education. --A talk by Dr. Sarada Herke. The venue is "The Spotted Mallard" in Melbourne Australia. Many thanks to Natalie and Andrea from The Laborastory (http://thelaborastory.com/) YouTube Channel (https://www.youtube.com/channel/UCqXXF1eMTiWlUdcG7jePcwQ) and to The Spotted Mallard for hosting the event (http://www.spottedmallard.com/events/tag/laborastory) Video Production by: Giuseppe Geracitano (goo.gl/O8TURb) </video> <video> Graph Theory: 66. Basic Bound on the Chromatic Number Description: In this video we prove by induction that every graph has chromatic number at most one more than the maximum degree. Odd cycles and complete graphs are examples for which the chromatic number meets this upper bound exactly. For other graphs, Brook's Theorem tells us that the chromatic number is at most the maximum degree. We will prove Brook's Theorem in a later video. -- Bits of Graph Theory by Dr. Sarada Herke. Related videos: https://youtu.be/4FE79y_JkCE - Graph Theory: 64. Vertex Colouring https://youtu.be/FrJve7fuEoQ - Graph Theory: 65. 2-Chromatic Graphs </video> <video> Graph Theory FAQs: 04. Isomorphism vs Homomorphism Description: In this video we recall the definition of a graph isomorphism and then give the definition of a graph homomorphism. Then we look at two examples of graph homomorphisms and discuss a special case that relates to graph colourings. -- Graph Theory FAQs by Dr. Sarada Herke. Related videos: GT09 Graph Isomorphisms - https://youtu.be/yFpRpxOry-A GT10 Isomorphic and NonIsomorphic Graphs - https://youtu.be/z-GfKbzvtBA FAQ03 Isomorphism Using Adjacency Matrix - https://youtu.be/UCle3Smvh1s For quick videos about Math tips and useful facts, check out my other channel "Spoonful of Maths" - http://youtube.com/spoonfulofmaths Video Production by: Giuseppe Geracitano (goo.gl/O8TURb) </video> <video> Graph Theory: 63. Petersen Graph is Non-Planar Description: In this video we give two proofs for why the Petersen graph is non-planar. -- Bits of Graph Theory by Dr. Sarada Herke. Related videos: GT62 Graph Minors and Wagner's Theorem - https://youtu.be/2hkLC2q2wT4 GT61 Characterization of Planar Graphs - https://youtu.be/UkjJE3bmPV0 GT57 Planar Graphs - https://youtu.be/wnYtITkWAYA For quick videos about Math tips and useful facts, check out my other channel "Spoonful of Maths" - http://youtube.com/spoonfulofmaths Video Production by: Giuseppe Geracitano (goo.gl/O8TURb) </video> <video> Graph Theory FAQs: 03. Isomorphism Using Adjacency Matrix Description: An isomorphism from a graph G to a graph H is a bijection from the vertex set of G to the vertex set of H such that adjacency and non-adjacency are preserved. However, finding such a mapping is also equivalent to find a permutation matrix P such that A = PBP^T where A and B are the adjacency matrices of G and H respectively. We demonstrate how this works with an example. -- Graph Theory FAQs - by Dr. Sarada Herke. Related videos: GT09 Graph Isomorphisms - https://youtu.be/yFpRpxOry-A GT07 Adjacency and Incidence Matrices - https://youtu.be/LUDNz2bIjWI FAQ Graph Automorphisms - https://youtu.be/X4_4Bqj6EdA For quick videos about Math tips and useful facts, check out my other channel "Spoonful of Maths" - http://youtube.com/spoonfulofmaths Video Production by: Giuseppe Geracitano (goo.gl/O8TURb) </video> <video> Graph Theory: 61. Characterization of Planar Graphs Description: We have seen in a previous video that K5 and K3,3 are non-planar. In this video we define an elementary subdivision of a graph, as well as a subdivision of a graph. We then discuss the fact that if a graph G contains a subgraph which is a subdivision of a non-planar graph, then G is non-planar. The remarkable thing is that Kuratowski's Theorem says that the graphs containing subgraphs which are subdivisions of either K5 or K3,3 are the ONLY graphs which are non-planar. In otherwords, the characterization of planar graphs is: A graph G is planar if and only if it contains no subgraph which is a subdivision of either K5 or K3,3. The proof of Kuratowski's Theorem is very long and detailed, and is omitted here. -- Bits of Graph Theory by Dr. Sarada Herke. Related videos: GT60 Non-Planar Graphs - https://youtu.be/-m6Dq7v9ToM GT59 Maximal Planar Graphs - https://youtu.be/_d_6JvceAwE GT58 Euler's Formula for Plane Graphs - https://youtu.be/5ywif1Zpeo4 GT57 Planar Graphs - https://youtu.be/wnYtITkWAYA For quick videos about Math tips and useful facts, check out my other channel "Spoonful of Maths" - http://youtube.com/spoonfulofmaths Video Production by: Giuseppe Geracitano (goo.gl/O8TURb) </video> <video> Graph Theory: 57. Planar Graphs Description: A planar graph is a graph that can be drawn in the plane without any edge crossings. Such a drawing (with no edge crossings) is called a plane graph. A given plane graph divides the plane into regions and each region has a boundary that outlines it. We look at some examples and also give an informal proof of the fact that the complete bipartite graph with partite sets of size 3 and 3 is not planar. -- Bits of Graph Theory by Dr. Sarada Herke. Related videos: https://youtu.be/71XbdtoG7P8 - Graph Theory: 04. Families of Graphs https://youtu.be/9nYjPdMUAsk - Do Maths with Pigeons and Handshakes For quick videos about Math tips and useful facts, check out my other channel "Spoonful of Maths" - http://youtube.com/spoonfulofmaths Video Production by: Giuseppe Geracitano (goo.gl/O8TURb) </video> <video> Graph Theory FAQs: 02. Graph Automorphisms Description: An automorphism of a graph G is an isomorphism between G and itself. The set of automorphisms of a graph forms a group under the operation of composition and is denoted Aut(G). The automorphisms of a graph describe the symmetries of the graph. We look at a few examples of graphs and determine their automorphisms. We also briefly look at how do find the automorphism group of a graph using Sage. -- Graph Theory FAQs by Dr. Sarada Herke. Related videos: https://youtu.be/yFpRpxOry-A - Graph Theory: 09. Graph Isomorphisms https://youtu.be/S1Zwhz-MhCs - Graph Theory: 02. Definition of a Graph For quick videos about Math tips and useful facts, check out my other channel "Spoonful of Maths" - http://youtube.com/spoonfulofmaths </video> <video> Graph Theory: 59. Maximal Planar Graphs Description: In this video we define a maximal planar graph and prove that if a maximal planar graph has n vertices and m edges then m = 3n-6. We use this to show that any planar graph with n vertices has at most 3n-6 edges. -- Bits of Graph Theory by Dr. Sarada Herke. Related videos: GT57 Planar Graphs - https://youtu.be/wnYtITkWAYA GT58 Euler's Formula for Plane Graphs - http://youtu.be/5ywif1Zpeo4 For quick videos about Math tips and useful facts, check out my other channel "Spoonful of Maths" - http://youtube.com/spoonfulofmaths Video Production by: Giuseppe Geracitano (goo.gl/O8TURb) </video>

Contacts and Links

Description

This channel is created to provide free and easy access to graduate level topics in Mathematics, mostly focused on Combinatorics and Graph Theory.
My name is Sarada Herke, I have a MSc. in Mathematics from the University of Victoria and a PhD from the University of Queensland, specializing in Graph Theory.

Videos from channel