Graph theory-some details about null graph

Questions

  • 1

    Doubt about example shown in video

    sachinmittal.mittal1@gmail.com
    Reply

    Sir you said that vertex connectivity should be n-1 for a complete graph so then it degrades down to a single vertex which is still connected right ?
    So here also you cant disconnect complete graph

    • Laxmi K

      We can not disconnect the complete graph. That’s why vertex connectivity is defined as n-1 in the literature. you can assume it as an exception.

  • 1

    doubt

    kaustavpro19
    Reply

    So,In case of complete graph which is an exception we will end up in single vertex always and we should consider single vertex as a disconnect graph?

    • getgatebook

      No single vertex is always a connected graph.

  • 1

    doubt

    tarunsuripro20
    Reply

    Sir Every k-connected graph is k-1 connected, can you tell me is this true or false?

    • getgatebook

      A graph G is said to be k-connected (or k-vertex connected, or k-point connected) if there does not exist a set of k-1 vertices whose removal disconnects the graph, i.e., the vertex connectivity of G is >=k

      In such graph there doesn’t exist a set of vertices of k-2 vertices whose removal disconnects the graph. So obviously it is k-1 connected too.