Can't understand K-Truss Graph properties

Question

_{Cross-posted on Operations Research SE.}

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 it correct?

Answer 1

Your solution is consistent with the definition you gave. But note that the $k$-truss of a graph $G = (V,E)$ is usually defined as the maximal subgraph $H = (V',E')$ such that every edge of $H$ is in at least $k-2$ triangles within $H$ (not in the original graph). According to this definition, the $4$-truss of your example graph is empty.