# Triangle counting

To understand how the triangle counting can be represented by a polynomial, which is the form the sum check protocol described in Sum check - overview requires, it would be helpful to understand how the triangles can be represented using a adjacency matrix beforehand. The intuition around its matrix representation is fundamental to understanding its polynomial form from my view.

This post focuses explaining how to counting triangles in adjacency matrix, laying down the connection to the Sum check - benchmarks in which triangle counting will be applied into sum check protocol.

Below outlines the features of triangle counting using operations under matrix structure.

### Overview

Adjacency matrix is an representation of undirected graph to denote relationship between vertices and edges.

Before we dive into understanding how the graph works at low level, here are some high level implications for the triangle counting use case.

- The graph by an adjacency matrix by itself represents
*one walk*between vertices. - Having an adjacency matrix multiplied with itself, resulting in
, it is representing *two walks*between vertices. - Multiplying itself two times, resulting in
, it is representing *three walks*between vertices. - The values in the trace of the resulted matrix
are the number of round trips. Summing them up and divide by 6, equals to the total number of triangles that can be found in the graph. *The following will try to explain why it is the number 6.*

### Representation

Firstly, let's take a look at the polynomial representing triangle counting.

But what does this polynomial implies? What does

To clarify these questions, it would be helpful to take a look at the following examples of what they represent for

#### Trips of

This represents the counts of trips having one walk.

Corresponding, the following graph illustrates one walk paths.

flowchart LR 1 --> 2 & 3 2 --> 4 2 --> 3 3 --> 4

*Since the adjacency matrix is symmetry, so the arrow directions can be reversed.*

#### Trips of

This represents the counts of trips having two walks.

##### Round trip example

Corresponding, the following graph illustrates two walk paths for

flowchart LR 1 --> 2 & 3--> 1

The example above also can be represented by

##### Intermediate trip example

The values other than the ones from the trace of the matrix represent the number intermediate trips, instead of round trips.

For point

flowchart LR 2 --> 1 & 4--> 3

#### Trips of

This represents the number of trips having three walks. When it is a count for round trip, the value in the trace of

##### Round trip example

For the point

flowchart LR 2 --> 1 & 3 & 4--> 2

Seemingly, there only 3 round trips with two walks around vertice *2*. But keep in mind the

With the trips represented by

flowchart LR 2 --> 1 --> 3 --> 2

flowchart LR 2 --> 4 --> 3 --> 2

With

flowchart LR 2 --> 3 --> 1 --> 2

With

flowchart LR 2 --> 3 --> 4 --> 2

Thus, there are total 4 undirected round trips as the

### Matrix trace

Based on the method we observed in counting the round trips, to calculate the total number of triangles, it just need to sum up the values in the trace of

Because the adjacency matrix in our example is symmetry, so is undirected. The result

### Into polynomial

The implication of summing up the trace values of matrix multiplication result

In the Sum check - benchmarks, we will explain how this polynomial can be applied to the sum check protocol.