Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Question I found in one of the previous year's exam:

Let $G$ a connected graph on $n \geq 3$ vertices, such that every edge participates in at least one triangle. Prove that $|E(G)| \geq \dfrac{3(n-1)}{2}$.

I tried proving using Turan's theorem on $\overline{G}$, but I get a less tight bound - $|E(G)| > \dfrac{3(n-2)}{4}$.

Using induction I'm getting nowhere as well; here it seems like I need to break the problem to $n$ odd and even, as it gives different number of edges. And even then, I don't know which edge/vertex to contract/delete.

Is it more straightforward than that?

Thanks in advance.

share|improve this question
    
I can see why it would be true, but I'm a bit too rusty on my graph theory to come up with a formal proof. A tree, which of course is a connected graph with no cycles, takes n-1 edges. Now starting with each vertex of degree 1, complete each triangle. –  Mike Feb 10 '12 at 19:10
    
It's a good idea, and seems to work on some example trees I've done, but I can't come with a good generalization of this method to every tree (obviously, joining only leaves by edges isn't enough). –  Pavel Feb 10 '12 at 20:32
    
Well, the basic idea was that each time you add an edge to the tree, you include at most 2 edges of the tree into a 3-cycle. I guess this could be proved by contradiction. Assume adding an edge $v_1v_2$ would create 2 3-cycles $v_1v_2v_3$ and $v_1v_2v_4$. Then $v_1$ and $v_2$ are each connected to $v_3$ and $v_4$ and there exists a 4-cycle $v_1v_3v_2v_4$ which can't possibly occur if the graph is a tree. Therefore to include n-1 edges into 3-cycles requires adding at least $\frac{n-1}2$ edges. –  Mike Feb 10 '12 at 21:43

2 Answers 2

up vote 5 down vote accepted

The assumption that $G$ is connected is crucial.

Otherwise, consider a graph of $6$ vertices which is composed of $2$ disjoint triangles.

Also, it is not true that $\overline{G}$ needs to be triangle free (all you need is an independent set of size $3$ in $G$).

A proof by induction actually works.

Base cases

$n=3,4$ are easily verified.

Induction step

Suppose we are given a graph $G$ with $n \ge 5$ vertices. Let $e = |E(G)|$.

Now if every vertex of $G$ had degree $\ge 3$, then we are done, as $2e \ge 3n$.

So assume there is a vertex $a$ of degree exactly $2$. (Why not $0$ or $1$?).

Let $b,c$ be the neighbours of $a$. Note that $\{b,c\}$ is an edge in $G$ (Why?)

Consider two cases:

Case 1) The edge $\{b,c\}$ is a part of a triangle other than $abc$.

In which case, we delete $a$ from $G$ to give a new graph $G'$ of $n-1$ vertices, satisfying the induction hypothesis.

Thus we get $e-2 \ge 3(n-2)/2$ and so $e \ge (3n - 2)/2 \gt 3(n-1)/2$ and so we are done.

Case 2) The edge $\{b,c\}$ is not part of any other triangle.

In this case, we delete the vertex $a$ and the edge $\{b,c\}$ to get a new graph $G'$.

Now it is possible that $G'$ is disconnected due to deletion of edge $\{b,c\}$. Since $G$ was connected, $G'$ has no more than two connected components, and we can try and apply the induction step to each connected component if each component has at least two vertices.

Thus if $n_1$ and $n_2$ (with $n_1 \ge 2$ and $n_2 \ge 2$) are the number of vertices in each connected component, we have that,

$e - 3 \ge 3(n_1 - 1)/2 + 3(n_2 -1)/2 = 3(n-3)/2$

Thus

$e \ge 3(n-1)/2$

and we are done.

If one of $n_1$, $n_2$ is $0$ or $1$, we can ignore that component and the above inequality still holds.

share|improve this answer
    
Thank you! Seems like the solution that I was looking for. –  Pavel Feb 11 '12 at 8:14

This post lacks the formalism necessary to constitute a formal proof (especially on an exam), but hopefully it gets you going in the right direction.

Suppose first that $n$ is odd. First, for terminology's sake, define $T_n$ to be the graph with $n$ vertices (we'll take $n$ odd) such that each edge participates in exactly one triangle. $T_3$ will be the standard triangle, and $T_n$ will in general, look like this:

enter image description here

It is not too hard to see that in the graph $T_n$, we have exactly $\frac{n-1}{2}$ triangles (this can be proved using an easy induction on odd $n$). Note that in such a graph, we have $$ |E| = 3 \cdot \# \text{triangles} = \frac{3(n-1)}{2}. $$

If $H$ is another "triangular" graph with $n$ vertices (still assuming $n$ is odd), then either $H$ is isomorphic to $T_n$, or $H$ has $T_n$ as a subgraph. This should establish the bound $|E| \geq \frac{3(n-1)}{2}$ for when $n$ is odd.

When $n$ is even, the same ideas should work, except we work not with the graph $T_n$, but rather with $T_n$ plus one vertex and plus two edges. We can call this new graph, say, $Z_n$:

enter image description here

Note that the number of triangles in $Z_n$ is now $\frac{n}{2} = \left\lceil \frac{n-1}{2} \right\rceil$, and hence the number of edges is then:

$$ 5 + \frac{3((n-3)-1)}{2}, $$ where we count first the 5 edges in the four vertices on the left, and then the remaining $n-3$ vertices as we did in the odd case. This gives that the total number of edges is then

$$ |E| \geq 5 + \frac{3(n-4)}{12} = \frac{3n -2}{2} = \left\lceil \frac{3(n-1)}{2} \right\rceil. $$

I apologize again for the lack of precision here, but hopefully this helps.

share|improve this answer
    
Thanks! Solution by exhaustion may work here as well, but I'll have to go with the solution of Aryabhata. –  Pavel Feb 11 '12 at 8:18
    
No problem. Aryabhata's solution is much nicer, and it is probably closer to what was intended. –  JavaMan Feb 11 '12 at 16:13

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.