Results 1 to 3 of 3

Math Help - Graph Theory

  1. #1
    Senior Member
    Joined
    Apr 2006
    Posts
    401

    Exclamation Graph Theory

    NOTE: the compositions (3) for instance and (1,6) are subscripts.

    How many triangles (=K(3)) does K(1,6) [with a horizontal line above K(1,6)], the complement of K(1,6), have?

    How many triangles does K(1,n) [again, a horiz. line over K(1,n)], the complement of K(1,n), have?

    These problems are from a section on Graph Theory, involving the applications of matrices with graphs and so forth. Any help would be great. Thanks!

    Apparently in the book it shows this as an easy problem, maybe something I am just not getting.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Jun 2005
    Posts
    295
    Awards
    1
    To find how many triangles a graph G has in general you can write down the adjacency matrix A, where A(i,j) = 1 if there is an edge between vertex i and vertex j, and 0 otherwise. Taking the square of the matrix A^2(i,j) counts the number of k such that there is an edge (i,k) and an edge (k,j). So A(i,j).A^2(i,j) counts the number of triangles containing (i,j) as an edge. Sum over all i,j and divide by 3.

    However in this case I think it's easier. K(1,n) is the complete bipartite graph on 1+n vertices, say 0,1,...,n with 0 connected to each of 1,...n. So its complement is simply the complete graph on 1,...n. It's easy to see that this has n(n-1)(n-2)/6 triangles.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Apr 2006
    Posts
    401
    Wow, thanks rgep. This makes complete sense; after discussing it with my professor, I am not sure how I would have thought of even going down that path.

    So, therefore, that formula works for all K? That is, K(1, 6) just has 20 triangles?

    Thank you for your help, rgep!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Graph theory, bipartite Graph
    Posted in the Math Topics Forum
    Replies: 2
    Last Post: March 10th 2012, 06:47 AM
  2. Graph Theory / Chromatic Number of a Complete Graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 15th 2011, 10:59 AM
  3. (Graph Theory)Prove that graph X is a tree.
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: August 1st 2011, 04:30 AM
  4. Replies: 0
    Last Post: September 25th 2010, 06:59 AM
  5. Graph Theory - Size of a Line Graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: July 26th 2010, 12:15 AM

Search Tags


/mathhelpforum @mathhelpforum