SOLUTIONS

Graph Components and Connectivity
A graph may not be fully connected. For instance, only about 25% of the web graph is estimated to be in the largest strongly connected component. Another 25% is estimated to be in the incomponent and 25% in the outcomponent of the strongly connected core. The remaining 25% is made up of smaller isolated components. For social graphs, one is often interested in core components that indicate groups of people that are connected in a limited way.
ReferenceReference
Connected Components
ConnectedComponents — give groups of vertices that are strongly connected
KCoreComponents — give groups of vertices that are connected to at least others
ConnectedGraphQ — test whether a graph is connected
Vertex Components
VertexComponent — give the component for a set of vertices
VertexOutComponent — give the outcomponent for a set of vertices
VertexInComponent — give the incomponent for a set of vertices
Vertex Connectivity
FindVertexCut — find a minimal set of vertices that, if cut, makes the graph disconnected
VertexConnectivity — minimal number of vertices to cut to disconnect the given graph
Edge Connectivity
FindEdgeCut — find a minimal set of edges that, if cut, makes the graph disconnected
EdgeConnectivity — minimal number of edges to cut to disconnect the given graph
Cuts and Partitions
FindMinimumCut — find a partition of vertices that minimize the edges to cut
FindGraphPartition — find a balanced partition of vertices that minimizes the edges to cut