Results 1 to 2 of 2

Thread: 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
    3,387
    Thanks
    1345

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

    The adjacency matrix is symmetric across its diagonal. So, when multiplying $\displaystyle A\cdot A$, consider the first column of $\displaystyle A$ times the first row of $\displaystyle 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 $\displaystyle a_{2,1}$ of $\displaystyle A^2$, you get the number of vertices adjacent to both $\displaystyle v_1$ and $\displaystyle v_2$. Similarly for the rest of the entries.

    Now, what happens when you multiply $\displaystyle A^2$ by $\displaystyle A$? The top row of $\displaystyle A^2$ lists the number of vertices adjacent to both $\displaystyle v_1$ and $\displaystyle v_k$ for each position $\displaystyle a_{1,k}$. Each vertex that is adjacent to both $\displaystyle v_1$ and $\displaystyle v_k$ forms a triangle. When you multiply this by the first column of $\displaystyle A$, the entry $\displaystyle a_{1,1}$ of $\displaystyle A^3$ will have twice the number of triangles adjacent to $\displaystyle v_1$. I say twice because if we have a triangle $\displaystyle v_1v_iv_j$, it will be counted by both $\displaystyle v_i$ and $\displaystyle v_j$, but since $\displaystyle a_{1,1} = 0$ in $\displaystyle A$ (since $\displaystyle v_1$ is not considered adjacent to itself), the triangle $\displaystyle v_1v_iv_j$ will not be counted by $\displaystyle v_1$ itself. So, in $\displaystyle a_{1,1}$, you have twice the number of triangles adjacent to $\displaystyle v_1$. In $\displaystyle a_{i,i}$ you get twice the number of triangles adjacent to $\displaystyle v_i$ (which includes the same triangle already counted twice in $\displaystyle a_{1,1}$. Then, that same triangle is counted another two times in $\displaystyle 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; Oct 21st 2013 at 11:11 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

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

Search Tags


/mathhelpforum @mathhelpforum