Maximum Number of Edges in a Directed Graph

Last Updated : 12 May, 2024

In a directed graph, edges have a direction associated with them meaning they point from the one vertex to another. The maximum number of edges in the directed graph depends on the number of the vertices and type of graph.

Without Self-loops and Parallel Edges:

In a directed graph without self-loops and parallel edges each vertex can have an edge to the every other vertex except itself. The maximum number of the edges E max in such a graph with the V vertices is given by the formula:

E max=V×(V−1)

Implementation:

C++

#include <iostream>
using namespace std;

// Function to return the maximum number of directed edges
// if self loops and parallel edges are not allowed
int GFG(int V) { return V * (V - 1); }
int main()
{
    int V = 5;
    int maxEdges = GFG(V);
    cout << "Maximum number of edges without self-loops "
            "and parallel edges: "
         << maxEdges << endl;
    return 0;
}

Java

public class Main {
    // Function to return the maximum number of directed
    // edges if self loops and parallel edges are not
    // allowed
    public static int maxEdges(int V)
    {
        return V * (V - 1);
    }

    public static void main(String[] args)
    {
        int V = 5;
        int maxEdges = maxEdges(V);
        System.out.println(
            "Maximum number of edges without self-loops and parallel edges: "
            + maxEdges);
    }
}

Python

# Function to return the maximum number of directed edges
# if self loops and parallel edges are not allowed


def GFG(V):
    return V * (V - 1)


def main():
    V = 5
    maxEdges = GFG(V)
    print("Maximum number of edges without self-loops "
          "and parallel edges:", maxEdges)


if __name__ == "__main__":
    main()

    # This code is contributed by Ayush Mishra

JavaScript

function maxEdges(V) {
    return V * (V - 1);
}

function main() {
    const V = 5;
    const maxEdgesValue = maxEdges(V);
    console.log("Maximum number of edges without self-loops and parallel edges: " + maxEdgesValue);
}

// Call the main function
main();

Output

Maximum number of edges without self-loops and parallel edges: 20

With Self-loops and Without Parallel Edges:

In this case, each vertex can have an edge to the every other vertex including itself but parallel edges are not allowed. The maximum number of edges E max in such a graph with the V vertices is given by the formula:

E max = V×V

Implementation:

C++

#include <iostream>
using namespace std;

// Function to return the maximum number of directed edges
// if self loops are allowed and parallel edges are not
// allowed
int GFG(int V) { return V * V; }
int main()
{
    int V = 5;
    int maxEdges = GFG(V);
    cout << "Maximum number of edges with self-loops and "
            "without parallel edges: "
         << maxEdges << endl;
    return 0;
}

Java

public class Main {
    // Function to return the maximum number of directed
    // edges if self loops are allowed and parallel edges
    // are not allowed
    public static int GFG(int V) { return V * V; }

    public static void main(String[] args)
    {
        int V = 5;
        int maxEdges = GFG(V);
        System.out.println(
            "Maximum number of edges with self-loops and without parallel edges: "
            + maxEdges);
    }
}
// This code is contributed by Prachi.

Python

# Function to return the maximum number of directed edges
# if self loops are allowed and parallel edges are not
# allowed
def GFG(V):
    return V * V

if __name__ == "__main__":
    V = 5
    max_edges = GFG(V)
    print("Maximum number of edges with self-loops and without parallel edges:", max_edges)

JavaScript

// Function to return the maximum number of directed edges
// if self loops are allowed and parallel edges are not
// allowed
function maxEdges(V) {
    return V * V;
}

// Main function
function main() {
    let V = 5;
    let maxEdgesValue = maxEdges(V);
    console.log("Maximum number of edges with self-loops and without parallel edges: " + maxEdgesValue);
}

// Call the main function
main();

Output

Maximum number of edges with self-loops and without parallel edges: 25

Maximum number of edges in Bipartite graph

maha123

Improve

Maximum Number of Edges in a Directed Graph

Without Self-loops and Parallel Edges:

With Self-loops and Without Parallel Edges:

Similar Reads

What kind of Experience do you want to share?