# What does a wedge in a graph look like?

I am reading Decompositions of Triangle-Dense Graphs by Gupta et al.

On page 2, in Definition 1 what is a wedge in a graph?

I know what triangle is but I don't know what wedge is and google isn't helping!

They say it in the paper.

Let a wedge be a two-hop path in an undirected graph.

So it is a path with 2 edges, like 2/3 of a triangle.

Right before the definition the authors define a wedge to be a two-hop path in an undirected graph. After the definition, they note that every triangle of a graph contains 3 wedges. In other words, with a wedge they mean a path $P_3$.

• Or $P_2$, depending on whether you name your paths after the number of edges or number of vertices they contain. Isn't it more common to count the edges? – David Richerby Feb 9 '14 at 19:53
• @DavidRicherby It's definitely more common to count the vertices. Similar notation is used e.g. for complete graphs, cycles, stars and wheels ($K_n$, $C_n$, $S_n$, $W_n$). This way it's more natural to define small graphs (think of say $P_1$). Also, it's not that easy to specify say wheels or complete graphs by edge count. – Juho Feb 10 '14 at 9:17
• Are you sure it's more common for paths? All the graph theory books on my shelf (Bollobas, Modern Graph Theory; Diestel, Graph Theory; and Hell and Nesetril, Graphs and Homomorphisms) define a $k$-path to have $k$ edges and $k+1$ vertices. – David Richerby Feb 10 '14 at 14:08
• @DavidRicherby I'd say so yes, at least if the notation is precisely $P_n$ (Diestel seems to use $P^k$, where $k$ stands for the number of edges). ISGCI uses $P_3$ to mean a path on 3 vertices, as does Wolfram MathWorld and Wikipedia. – Juho Feb 10 '14 at 14:56
• Yeah, Diestel uses $P^k$, $K^k$ etc. so he can write things like "Let $P_1, \dots, P_k$ be the $k$ distinct paths between $S$ and $T$." – David Richerby Feb 10 '14 at 15:03

A nice and easy explanation of wedges is available the paper "Triadic Measures on Graphs: The Power of Wedge Sampling" SDM, 2013.

• Welcome to the site! Given that a wedge is just a 2-path, I'm not sure much more explanation is needed. :-) But please give a full citation and a link to the paper, in any case. – David Richerby Nov 28 '16 at 8:28