Scribd Logo
Upload

Welcome to Scribd!

  • 19 views

    3rd Year Mathematics-Discrete Mathematics: 1 Graph Theory

    Uploaded by

    SUSHIL
    The document proves that for a simple graph with n vertices and m components, the maximum number of edges is 1/2(n - m)(n - m + 1). It shows that each component can have at most the number of edges of a complete graph of the same number of vertices. By summing over all components and applying algebraic manipulations, it derives the claimed upper bound on the total number of edges.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    3rd Year Mathematics-Discrete Mathematics: 1 Graph Theory

    Uploaded by

    SUSHIL
    19 views1 page
    The document proves that for a simple graph with n vertices and m components, the maximum number of edges is 1/2(n - m)(n - m + 1). It shows that each component can have at most the number of edges of a complete graph of the same number of vertices. By summing over all components and applying algebraic manipulations, it derives the claimed upper bound on the total number of edges.

    Original Description:

    mathematics

    Original Title

    Discrete Mathematics

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document proves that for a simple graph with n vertices and m components, the maximum number of edges is 1/2(n - m)(n - m + 1). It shows that each component can have at most the number of edges of a complete graph of the same number of vertices. By summing over all components and applying algebraic manipulations, it derives the claimed upper bound on the total number of edges.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    19 views1 page

    3rd Year Mathematics-Discrete Mathematics: 1 Graph Theory

    Uploaded by

    SUSHIL
    The document proves that for a simple graph with n vertices and m components, the maximum number of edges is 1/2(n - m)(n - m + 1). It shows that each component can have at most the number of edges of a complete graph of the same number of vertices. By summing over all components and applying algebraic manipulations, it derives the claimed upper bound on the total number of edges.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 1

    3rd year Mathematics-Discrete Mathematics

    Graph Theory

    Theorem 1.1. Show that a simple graph with n vertices and m components can have at most
    1
    2 (n m)(n m + 1) edges.
    Proof.

    Let G be a simple graph with m components C1 , C2 ,...., Cm .

    Let ni be the number of vertices in the component Ci for i = 1, 2, ...., m.


    Then n1 + n2 + .... + nm = n.
    Since Ci is a simple graph, the maximum possible number of edges in Ci is
    Hence the number of edges in G is less than or equal to

    m
    1
    (ni 2
    2
    i=1

    ni (ni 1)
    .
    2

    ni )

    Now for any m positive integers n1 , n2 ,..., nm , we have


    (n1 1) + (n2 1) + ... + (nm 1) = n1 + n2 + ... + nm m.
    Squaring both the sides we obtain
    (n1 1)2 + ... + (nm 1)2 + 2

    (ni 1)(nj 1) = (n1 + ... + nm )2 2(n1 + ... + nm )m + m2 .

    i,j=1
    i=j

    whence
    m

    (ni 1)(nj 1)
    n1 2 + n2 2 + ... + nm 2 2(n1 + n2 + ... + nm ) + m + 2
    i,j=1
    i=j

    = (n1 + n2 + ... + nm )2 2(n1 + n2 + ... + nm )m + m2 .


    Hence
    n1 2 + n2 2 + ... + nm 2 (n1 + n2 + ... + nm )2 2(n1 + n2 + ... + nm )(m 1) + (m2 m)
    So the number of edges in G is less than or equal to
    1 2
    (ni ni )
    2
    m

    i=1

    +
    =
    =

    1
    (n1 + n2 + .... + nm )2 (n1 + n2 + .... + nm )(m 1)
    2
    1
    1 2
    (m m) n
    2
    2
    1 2
    1
    (n n) n(m 1) + (m2 m)
    2
    2
    1
    (n m)(n m + 1)
    2

    You might also like