Can't understand K-Truss Graph properties

Question

_{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?

Answer 1

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.

source: Li, Z., Lu, Y., Zhang, WP. et al. Discovering Hierarchical Subgraphs of K-Core-Truss. Data Sci. Eng. 3, 136–149 (2018)

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

source: A. Conte, D. De Sensi, R. Grossi, A. Marino and L. Versari, "Truly Scalable K-Truss and Max-Truss Algorithms for Community Detection in Graphs," in IEEE Access, vol. 8, pp. 139096-139109, 2020

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/