Question

Suppose \(G\) is a simple graph with \(p\) vertices and \(q\) edges.Prove that this graph has at least \(\large q(\frac{2q}{p} - 1 )\) paths with the length 2.

Answer 1

help me and ill help you

Answer 2

for example this is a path with length 2:

Answer 3

*

Answer 4

@SithsAndGiggles

Answer 5

define simple graph

Answer 6

i have some idea...maybe we know that the numbers of these paths are \[\Large\sum_{v \in V}^{} \left(\begin{matrix}\deg(v) \\ 2\end{matrix}\right)\]

Answer 7

are loops allowed

Answer 8

as we can say that we chose 2 of the vertices

Answer 9

@dan815 , hmm what do u mean?

Answer 10

im asking definition of simple graph

Answer 11

He means can we have a situation like this: