# Can't understand K-Truss Graph properties

Cross-posted on Mathematics SE.

Since I have to implement an algorithm in the language of linear algebra, I'm trying to understand K-Truss Graphs which are defined as such

The k-truss is a subset of the graph with the same number of vertices, where each edge appears in at least $$𝑘 − 2$$ triangles in the original graph.

Given this example:

The $$4$$-Truss should be $$2-1-4$$ since we want edges present in at least $$2$$ triangles of the original graph:

• edge $$1-2$$ is present in triangle $$0-1-2$$ and triangle $$1-2-4.$$
• edge $$1-4$$ is present in triangle $$1-3-4$$ and triangle $$1-2-4.$$

Is the solution given on my example correct?

• I don't think your example is correct. From this description, a 'truss' is a subgraph of some original graph. A k-truss requires that every edge $e$ in your truss, is supported by at least k-2 edges that are also part of the truss and that form triangles with edge $e$. In the example that you gave for the subgraph induced by vertices {1,2,4}, edge (0,1) cannot be a supporting edge as it is not part of the subgraph. Aug 19 at 0:25
• The subgraph induced by vertices {1,2,4} is however a 3-truss because every edge {(1,4),(2,4),(1,2)} is part of at least 1 triangle made up of nodes that are part of the truss. Aug 19 at 0:29
• Thanks for the answer Joris, so, {0,1,2} and {1,3,4} are also 3-truss, is that correct? Aug 19 at 10:01
• @TheSimpliFire sorry didn't know this rule, thanks for the edit Aug 19 at 14:48

The definition of a k-truss you are working with seems to deviate from the 'standard' definition. See below for a few different definitions that boil down to the same thing.

A k-truss of a graph $$G$$ is the largest subgraph of $$G$$ such that each edge is contained in at least $$k−2$$ triangles in this subgraph.

A k-truss is an inclusion-maximal subgraph $$H$$ in which each edge belongs to at least $$k - 2$$ triangles inside $$H$$

As I stated in the comments earlier, the subgraph induced by vertex set $$\{2,1,4\}$$ is not a 4-truss because that would require that every edge in your induced subgraph, is contained in 2 different triangles which must also be contained in the subgraph. In your case, edge $$(1,2)$$ is only contained in 1 triangle.

Following the above definitions, the subgraph induced by vertex set $$\{2,1,4\}$$ is not a 3-truss either, because it is not maximal. A 3-truss of your graph, would be the entire graph, since that is the largest subgraph in which every edge is part of at least 1 triangle in your subgraph.

Your graph does not contain a k-truss with $$k\geq 4$$.

Edit: as often in mathematics, there are inconsistencies in definitions. The definitions I cited above, explicitly require a k-truss to be the largest subgraph or an inclusion-maximal subgraph $$H$$ s.t. every edge in $$H$$ is covered by at least $$k-2$$ triangles in $$H$$. Note that there's a difference between largest (read: maximum) and maximal subgraph. Moreover, some works seem to drop this 'maximal' requirement and refer to a k-truss as any (not necessarily maximal) subgraph $$H$$ s.t. every edge in $$H$$ is covered by at least $$k-2$$ triangles in $$H$$, see e.g.: https://louridas.github.io/rwa/assignments/finding-trusses/

• perfectly explained, thank you again! Aug 19 at 21:54