To ensure that any two vertices are reachable from each other, the graph must have at least n-1 edges. This minimum is achieved when the graph forms a tree-like structure, such as a star graph, where edges connect vertices without forming cycles.
Conditions: G is an undirected graph.; G has n vertices.; G is a connected graph.
To ensure that any two vertices are reachable from each other, the graph must have at least n-1 edges. This minimum is achieved when the graph forms a tree-like structure, such as a star graph, where edges connect vertices without forming cycles.
Conditions: G is an undirected graph.; G has n vertices.; G is a connected graph.
In an undirected graph, there can be at most one edge between any pair of distinct vertices. The maximum number of edges is achieved by a complete graph, which equals the total number of unordered pairs of vertices, calculated as n(n−1)/2.
Conditions: G is an undirected graph.; G has n vertices.; We seek the possible maximum number of edges.
In an undirected graph, there can be at most one edge between any pair of distinct vertices. The maximum number of edges is achieved by a complete graph, which equals the total number of unordered pairs of vertices, calculated as n(n−1)/2.
Conditions: G is an undirected graph.; G has n vertices.; We seek the possible maximum number of edges.
To ensure mutual reachability between every pair of vertices, the directed graph must contain at least one directed cycle that covers all n vertices. A directed cycle with n vertices has exactly n edges, which is the minimum required for strong connectivity.
Conditions: G is a directed graph.; G has n vertices.; G is a strongly connected graph.
To ensure mutual reachability between every pair of vertices, the directed graph must contain at least one directed cycle that covers all n vertices. A directed cycle with n vertices has exactly n edges, which is the minimum required for strong connectivity.
Conditions: G is a directed graph.; G has n vertices.; G is a strongly connected graph.
To maximize the number of edges while keeping the graph disconnected, the extremal construction isolates exactly one vertex and forms a complete graph with the remaining n-1 vertices. The number of edges is therefore the maximum for a complete graph on n-1 vertices, which is (n-1)(n-2)/2.
Conditions: G is an undirected graph.; G has n vertices.; G is a disconnected graph.
To maximize the number of edges while keeping the graph disconnected, the extremal construction isolates exactly one vertex and forms a complete graph with the remaining n-1 vertices. The number of edges is therefore the maximum for a complete graph on n-1 vertices, which is (n-1)(n-2)/2.
Conditions: G is an undirected graph.; G has n vertices.; G is a disconnected graph.
Unlike an undirected graph, a directed graph allows two oppositely directed edges between the same pair of distinct vertices. Therefore, the maximum number of edges is exactly twice the maximum number of edges in an undirected complete graph, yielding n(n−1).
Conditions: G is a directed graph.; G has n vertices.; We are seeking the maximum possible number of edges.
Unlike an undirected graph, a directed graph allows two oppositely directed edges between the same pair of distinct vertices. Therefore, the maximum number of edges is exactly twice the maximum number of edges in an undirected complete graph, yielding n(n−1).
Conditions: G is a directed graph.; G has n vertices.; We are seeking the maximum possible number of edges.