Graph Theory - Complete Course on Fundamentals and Advanced Topics

Graph Theory - Complete Course on Fundamentals and Advanced Topics

Wrath of Math via YouTube Direct link

Size and Degree from Vertex Deleted Subgraphs | Graph Theory

26 of 168
Previous
Next

26 of 168

Size and Degree from Vertex Deleted Subgraphs | Graph Theory

Class Central Classrooms beta

YouTube videos curated by Class Central.

Classroom Contents

Graph Theory - Complete Course on Fundamentals and Advanced Topics

Automatically move to the next video in the Classroom when playback concludes
  1. 1 What is a Graph? | Graph Theory
  2. 2 What are Adjacent Vertices? | Graph Theory
  3. 3 What is the Order of a Graph? | Graph Theory
  4. 4 What is the Size of a Graph? | Graph Theory
  5. 5 Order and Size of a Graph | Graph Theory
  6. 6 Empty Graph, Trivial Graph, and the Null Graph | Graph Theory
  7. 7 What are Adjacent Edges? | Graph Theory
  8. 8 What is a Subgraph? | Graph Theory
  9. 9 What is a Spanning Subgraph? | Graph Theory
  10. 10 Proper and Improper Subgraphs | Graph Theory
  11. 11 What is a Vertex Induced Subgraph? | Graph Theory
  12. 12 What is an Edge-Induced Subgraph? | Graph Theory
  13. 13 What is a Walk? | Graph Theory
  14. 14 What is a Trail? | Graph Theory
  15. 15 What is a Path? | Graph Theory
  16. 16 Proof: If There is a u-v Walk then there is a u-v Path | Every Walk Contains a Path, Graph Theory
  17. 17 What is a Circuit? | Graph Theory
  18. 18 What is a Graph Cycle? | Graph Theory, Cycles, Cyclic Graphs, Simple Cycles
  19. 19 Connected and Disconnected Graphs | Graph Theory
  20. 20 What are Connected Vertices? | Graph Theory
  21. 21 What are Connected Graphs? | Graph Theory
  22. 22 Connection as an Equivalence Relation | Graph Theory
  23. 23 What is a Component of a Graph? | Connected Components, Graph Theory
  24. 24 Explaining Components of Graphs | Graph Theory
  25. 25 Graphs Have at Least n-m Components | Graph Theory
  26. 26 Size and Degree from Vertex Deleted Subgraphs | Graph Theory
  27. 27 Distance, Diameter, and Geodesics | Graph Theory
  28. 28 Distance Between Two Vertices in Graphs | Graph Theory
  29. 29 What are Geodesics? | Graph Theory
  30. 30 Diameter of a Graph | Graph Theory
  31. 31 Proof: Connected Graph Contains Two Non-Cut Vertices | Graph Theory, Connected Graphs
  32. 32 What is a Path Graph? | Graph Theory
  33. 33 What are Cycle Graphs? | Graph Theory, Graph Cycles, Cyclic Graphs
  34. 34 What is a Complete Graph? | Graph Theory
  35. 35 Number of Edges in a Complete Graph (Using Combinations) | Graph Theory, Combinatorics
  36. 36 How Many Graphs on n Vertices? | Graph Theory
  37. 37 What is the Complement of a Graph? | Graph Theory, Graph Complements, Self Complementary Graphs
  38. 38 Proof: A Graph or its Complement Must be Connected | Graph Theory, Graph Complements
  39. 39 What is a Bipartite Graph? | Graph Theory
  40. 40 Proof: Closed Odd Walk contains Odd Cycle | Graph Theory
  41. 41 Proof: Bipartite Graphs have no Odd Cycles | Graph Theory, Bipartite Theorem, Proofs
  42. 42 Proof: If a Graph has no Odd Cycles then it is Bipartite | Graph Theory, Bipartite Theorem
  43. 43 How to Tell if Graph is Bipartite (by hand) | Graph Theory
  44. 44 What are Complete Bipartite Graphs? | Graph Theory, Bipartite Graphs
  45. 45 Intro to Hypercube Graphs (n-cube or k-cube graphs) | Graph Theory, Hypercube Graph
  46. 46 Overview of Loops in Graph Theory | Graph Loop, Multigraphs, Pseudographs
  47. 47 Intro to Directed Graphs | Digraph Theory
  48. 48 Parallel Edges in Multigraphs and Digraphs | Graph Theory, Multiple Edges, Multisets
  49. 49 What is the Degree of a Vertex? | Graph Theory
  50. 50 Neighborhood of a Vertex | Open and Closed Neighborhoods, Graph Theory
  51. 51 The First Theorem of Graph Theory | Graph Theory
  52. 52 Proof: Every Graph has an Even Number of Odd Degree Vertices | Graph Theory
  53. 53 Proof: Degree Sum Condition for Connected Graphs | Connected Graphs, Nonadjacent Vertices
  54. 54 Proof: Minimum Degree Condition for Connected Graphs | Graph Theory
  55. 55 What are Regular Graphs? | Graph Theory
  56. 56 What are Cubic Graphs? | Graph Theory
  57. 57 Simple Definition of Petersen Graph | Graph Theory
  58. 58 Degree Sequence of a Graph | Graph Theory, Graphical Sequences
  59. 59 Which Sequences are Graphical? (Degree Sequences and Havel-Hakimi algorithm) | Graph Theory
  60. 60 What are Irregular Graphs? (and why they are boring) | Graph Theory
  61. 61 What are Isomorphic Graphs? | Graph Isomorphism, Graph Theory
  62. 62 Isomorphic Graphs Have the Same Degree Sequence | Graph Theory
  63. 63 Graph Automorphisms and Vertex Transitive Graphs | Graph Theory
  64. 64 Edge Subtraction and Bridges in Graphs | Graph Theory, Edge Deletion
  65. 65 What are Bridges of Graphs? | Graph Theory, Edge Deletion
  66. 66 Proof: An Edge is a Bridge iff it Lies on No Cycles | Graph Theory
  67. 67 Intro to Tree Graphs | Trees in Graph Theory, Equivalent Definitions
  68. 68 Proof: Graph is a Tree iff Unique Paths for Each Vertex Pair | Graph Theory, Tree Graphs
  69. 69 Proof: Tree Graphs Have at Least Two End Vertices | Graph Theory
  70. 70 Proof: Tree Graph of Order n Has Size n-1 | Graph Theory
  71. 71 Proof: Forest Graphs have n-k Edges | Graph Theory
  72. 72 Proof: Connected Graph of Order n Has at least n-1 Edges | Graph Theory
  73. 73 Proof: Every Connected Graph has a Spanning Tree | Graph Theory
  74. 74 Kruskal's Algorithm for Minimum Spanning Trees (MST) | Graph Theory
  75. 75 Prim's Algorithm for Minimum Spanning Trees (MST) | Graph Theory
  76. 76 Proof on Cut Vertices Incident with Bridges | Graph Theory
  77. 77 Important Theorem about Cut Vertices | Graph Theory
  78. 78 Proof of a Characterization of Cut Vertices | Graph Theory
  79. 79 Proof: A Furthest Vertex is not a Cut Vertex | Graph Theory, Connected Graphs
  80. 80 What are Non-Separable Graphs? | Graph Theory
  81. 81 Vertex Cuts in Graphs (and a bit on Connectivity) | Graph Theory
  82. 82 Vertex Connectivity of a Graph | Graph Theory
  83. 83 Simple Bounds on Vertex Connectivity | Graph Theory
  84. 84 Vertex Connectivity of the Petersen Graph | Graph Theory
  85. 85 Edge Cuts and Edge Connectivity | Graph Theory
  86. 86 Edge Connectivity of Complete Graphs | Graph Theory
  87. 87 What are Vertex Separating Sets? | Graph Theory
  88. 88 What are Vertex Disjoint Paths? | Graph Theory
  89. 89 Intro to Menger's Theorem | Graph Theory, Connectivity
  90. 90 Proof: Menger's Theorem | Graph Theory, Connectivity
  91. 91 Eulerian Circuits and Eulerian Graphs | Graph Theory
  92. 92 Unicursal Graphs and Unicursal Lines | Semi-Eulerian Trails, Graph Theory
  93. 93 Proof: Graph is Eulerian iff All Vertices have Even Degree | Euler Circuits, Graph Theory
  94. 94 Hamiltonian Cycles, Graphs, and Paths | Hamilton Cycles, Graph Theory
  95. 95 Proof: Ore's Theorem for Hamiltonian Graphs | Sufficient Condition for Hamilton Graphs, Graph Theory
  96. 96 Proof: Necessary Component Condition for Graphs with Hamiltonian Paths | Graph Theory
  97. 97 Proof: Necessary Component Condition for Hamiltonian Graphs | Graph Theory
  98. 98 Proof: Dirac's Theorem for Hamiltonian Graphs | Hamiltonian Cycles, Graph Theory
  99. 99 Indegree and Outdegree in Directed Graphs | Graph Theory
  100. 100 In-Neighborhoods and Out-Neighborhoods in Digraphs | Graph Theory
  101. 101 Orientations of Graphs | Directed Graphs, Digraph Theory
  102. 102 What are Symmetric Digraphs? | Graph Theory
  103. 103 First Theorem of Directed Graphs | Digraph Theory
  104. 104 Underlying Graphs of Digraphs | Directed Graphs, Graph Theory
  105. 105 Weakly Connected Directed Graphs | Digraph Theory
  106. 106 Strongly Connected Directed Graphs | Graph Theory
  107. 107 Intro to Tournament Graphs | Graph Theory
  108. 108 Transitive Tournaments (Directed Graphs) | Graph Theory
  109. 109 Proof: Tournament is Transitive iff it has No Cycles | Graph Theory
  110. 110 Proof for Distances from Tournament's Maximum Outdegree Vertex | Graph Theory
  111. 111 Proof: Every Tournament has Hamiltonian Path | Graph Theory
  112. 112 Proof: Vertices of Strong Tournament Lie on Triangles | Graph Theory
  113. 113 Matchings, Perfect Matchings, Maximum Matchings, and More! | Graph Theory
  114. 114 Perfect Matchings on Complete Graphs | Graph Theory
  115. 115 Hall's Theorem and Condition for Bipartite Matchings | Graph Theory
  116. 116 Proof: Hall's Marriage Theorem for Bipartite Matchings | Graph Theory
  117. 117 Proof: Regular Bipartite Graph is Balanced | Graph Theory
  118. 118 Proof: Regular Bipartite Graph has a Perfect Matching | Graph Theory
  119. 119 Edge Covers and Edge Covering Numbers of Graphs | Graph Theory
  120. 120 Independent Vertex Sets and Independence Numbers | Graph Theory
  121. 121 Vertex Covers and Vertex Covering Numbers | Graph Theory
  122. 122 Complement of Vertex Cover is Independent Vertex Set | Graph Theory
  123. 123 Complement of Independent Set is Vertex Cover | Graph Theory
  124. 124 What are Graph Decompositions? | Graph Decomposition, Graph Theory
  125. 125 What are Planar Graphs? | Graph Theory
  126. 126 Proof: Euler's Formula for Plane Graphs | Graph Theory
  127. 127 Proof: Upper Bound for the Size of Planar Graphs | Graph Theory
  128. 128 Every Planar Graph has a Vertex of Degree 5 or Less | Graph Theory
  129. 129 Which Complete Graphs are Planar? | Graph Theory
  130. 130 Edges that Lie on One Boundary of a Region in a Plane Graph | Graph Theory
  131. 131 Degree of a Face in a Plane Graph | Graph Theory
  132. 132 Vertex Colorings and the Chromatic Number of Graphs | Graph Theory
  133. 133 Chromatic Number of Bipartite Graphs | Graph Theory
  134. 134 Chromatic Number of Complete Graphs | Graph Theory
  135. 135 What is a Clique? | Graph Theory, Cliques
  136. 136 Does Chromatic Number n Imply Clique on n Vertices? | Graph Theory
  137. 137 Edge Colorings and Chromatic Index of Graphs | Graph Theory
  138. 138 Subtracting a Vertex from a Graph (Vertex Deletion) | Graph Theory
  139. 139 What are Star Graphs? | Graph Theory
  140. 140 What is a Highly Irregular Graph? | Locally Irregular Graph, Graph Theory
  141. 141 Graph Representation with an Adjacency Matrix | Graph Theory, Adjaceny Matrices
  142. 142 What is a Maximal Clique? | Graph Theory, Cliques, Maximal Cliques
  143. 143 A Proof on Hamiltonian Complete Bipartite Graphs | Graph Theory, Hamiltonian Graphs
  144. 144 Maximum and Maximal Cliques | Graph Theory, Clique Number
  145. 145 Proof: Non-Regular Graph has Adjacent Vertices with Distinct Degrees | Connected Graphs
  146. 146 Proof: Two Longest Paths Have a Common Vertex | Graph Theory, Connected Graphs
  147. 147 Proof: A Graph or its Complement is not Bipartite | Graph Theory, Bipartite Graphs
  148. 148 Proof: Graph with all Even Degree Vertices has no Bridges | Graph Theory
  149. 149 Proof: Complement of Regular Non-Eulerian Graph is Eulerian | Graph Theory, Euler Graphs
  150. 150 Minimum and Maximum Degree Vertices in Complement Graphs | Graph Complements, Graph Theory
  151. 151 Bound on the Sum of Minimum Degrees of Graphs and their Complements | Graph Theory Proofs
  152. 152 Proof: Connected Graph with a Bridge must have a Cut Vertex | Graph Theory
  153. 153 Proof: Cut Vertex is not a Cut Vertex of the Complement Graph | Graph Theory
  154. 154 Resolving Sets and Metric Dimension of Graphs | Graph Theory
  155. 155 What are the Maximum and Maximal Cliques of this Graph? | Graph Theory
  156. 156 Bipartite Graphs with Isolated Vertices | Graph Theory, Complete Bipartite Graphs
  157. 157 Proof: Graph with n Vertices and n-1 Edges is a Tree | Graph Theory
  158. 158 Proof: A Bridge is the Unique Path connecting its End Vertices | Graph Theory
  159. 159 Proof: Every Edge of a Tree is a Bridge | Graph Theory
  160. 160 Proof: Every Graph Contains Minimum Degree Length Path | Graph Theory
  161. 161 Proof: Graph has a Cycle Longer than its Minimum Degree | Graph Theory
  162. 162 Graphs are Metric Spaces | Graph Theory
  163. 163 Eccentricity of a Vertex | Graph Theory
  164. 164 Diameter and Radius of Graphs | Graph Theory
  165. 165 Graph Diameter is Bounded by Radius | Graph Theory
  166. 166 Diameter and Radius of Tree Graphs | Graph Theory
  167. 167 Eccentricities of Adjacent Vertices Differ by at Most 1 | Graph Theory
  168. 168 Dominating Sets and Domination Number of Graphs | Graph Theory

Never Stop Learning.

Get personalized course recommendations, track subjects and courses with reminders, and more.

Sign up for free
Someone learning on their laptop while sitting on the floor.