Results 1 to 5 of 5

Math Help - Finding min and max number of edges of a connected graph

  1. #1
    Member
    Joined
    Oct 2010
    Posts
    95

    Finding min and max number of edges of a connected graph

    A simple graph of 25 vertices and 6 connected components.
    What is the minimum and maximum number of edges can the graph have?

    Is there a formula to calculate the min and max? 25 vertices is too huge to draw and there are several possibilities for minimum number as well as maximum number of edges.

    Thanks.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1574
    Awards
    1
    Quote Originally Posted by xEnOn View Post
    A simple graph of 25 vertices and 6 connected components. What is the minimum and maximum number of edges can the graph have?
    A single vertex is a degenerate component. Think of five degenerate components and one with twenty vertices.
    If the one with twenty vertices is tree, does that give a minimum?
    Does \mathcal{K}_{20} give a maximum?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Oct 2010
    Posts
    95
    ohh...a graph has minimum edges when it is a tree. So Edges = 20-1 = 19, is the minimum number of edges.

    But for the maximum, how I can calculate the maximum edges when there are 20 vertices? It can have infinite number of edges wouldn't it?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member Matt Westwood's Avatar
    Joined
    Jul 2008
    From
    Reading, UK
    Posts
    807
    Thanks
    27
    A simple graph (which I presume this is or the q won't make sense) allows only one edge per vertex pair, and no loops.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Oct 2010
    Posts
    95
    Then the maximum number of edges for a graph of 20 vertices could be 20! ?
    Like Vertex A could join Vertex B, could also join Vertex C and form a complete graph?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Minimum number of edges in a graph of order n
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: October 12th 2011, 03:27 PM
  2. Graph Edges and Connectivity
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 3rd 2011, 04:55 AM
  3. Graph theory : coloring edges
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: January 28th 2011, 04:48 AM
  4. Replies: 5
    Last Post: June 22nd 2008, 10:20 PM
  5. Eulerian graph with even vertices and odd edges
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: October 23rd 2007, 03:12 PM

Search Tags


/mathhelpforum @mathhelpforum