Results 1 to 2 of 2

Math Help - 1/6 of trace(A^3)? [Graph theory]

  1. #1
    Junior Member
    Joined
    Jun 2007
    Posts
    62

    1/6 of trace(A^3)? [Graph theory]

    Hello,

    I've read somewhere that if A is an adjacency matrix then (1/6)*trace(A^3) equals the number of triangles in the graph. Can someone explain why?

    Thanks.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,930
    Thanks
    782

    Re: 1/6 of trace(A^3)? [Graph theory]

    The adjacency matrix is symmetric across its diagonal. So, when multiplying A\cdot A, consider the first column of A times the first row of A. Every 1 and every 0 is in the same spot. So, you get the degree of each vertex across the diagonal. What happens when the first column is multiplied with the second row? In position a_{2,1} of A^2, you get the number of vertices adjacent to both v_1 and v_2. Similarly for the rest of the entries.

    Now, what happens when you multiply A^2 by A? The top row of A^2 lists the number of vertices adjacent to both v_1 and v_k for each position a_{1,k}. Each vertex that is adjacent to both v_1 and v_k forms a triangle. When you multiply this by the first column of A, the entry a_{1,1} of A^3 will have twice the number of triangles adjacent to v_1. I say twice because if we have a triangle v_1v_iv_j, it will be counted by both v_i and v_j, but since a_{1,1} = 0 in A (since v_1 is not considered adjacent to itself), the triangle v_1v_iv_j will not be counted by v_1 itself. So, in a_{1,1}, you have twice the number of triangles adjacent to v_1. In a_{i,i} you get twice the number of triangles adjacent to v_i (which includes the same triangle already counted twice in a_{1,1}. Then, that same triangle is counted another two times in a_{j,j}. Taking the trace adds up all numbers on the diagonal. You get six times the count of triangles in the graph.
    Last edited by SlipEternal; October 21st 2013 at 11:11 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 0
    Last Post: March 30th 2012, 02:27 AM
  2. Graph Theory / Chromatic Number of a Complete Graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 15th 2011, 09: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, 03:30 AM
  4. Replies: 0
    Last Post: September 25th 2010, 05:59 AM
  5. Graph Theory - Size of a Line Graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: July 25th 2010, 11:15 PM

Search Tags


/mathhelpforum @mathhelpforum