# Graph Theory

Printable View

• Apr 30th 2006, 01:34 PM
AfterShock
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.
• Apr 30th 2006, 09:55 PM
rgep
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.
• May 2nd 2006, 08:12 PM
AfterShock
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!