4
$\begingroup$

I have the following problem:

Let $G$ be a simple graph with $n$ vertices and such that every cycle in $G$ has length $\leq3$. Then $e(G)\leq\dfrac{3(n-1)}{2}$. (where $e(G)$ is the number of edges of the graph $G$)

I think it could be a good idea to prove this by induction, but do not know how to use the bound for the length of the cycles.

$\endgroup$
4
  • $\begingroup$ I don't understand, if graph is simple how can it have 2 cycle? Or I don't understand the term simple. $\endgroup$
    – nonuser
    Commented Nov 3, 2017 at 15:06
  • $\begingroup$ Simple means that the graph is undirected, unweighted and is not a multigraph (graphs with more than one edge between vertices) $\endgroup$
    – plr
    Commented Nov 3, 2017 at 15:53
  • $\begingroup$ So the only cycles wich are possible are 3-cycles? $\endgroup$
    – nonuser
    Commented Nov 3, 2017 at 15:55
  • $\begingroup$ Yes, that's correct. Because 2-cycles will mean that 2 vertex are joined by 2 edges, and we do not allow them here. $\endgroup$
    – plr
    Commented Nov 3, 2017 at 16:31

1 Answer 1

3
$\begingroup$

Suppose graph has 3-cycles $C_1,C_2,...C_k$ and $\varepsilon$ edges. Each cycle has 3 edges and because of condition that each cycle is of length 3 every edge is in at most one 3-cycle. So we have $$ k\leq {\varepsilon\over 3}$$

Suppose graph has spanning sub tree $T$ which has exactly $n-1$ edges. Then each edge which is not in $T$ (we have $\varepsilon -n+1$ of those) must be on exactly one 3-cycle. But we can't have more those edges than the 3-cycles. So we have $$ \varepsilon -n+1\leq k \leq {\varepsilon\over 3} \Longrightarrow \varepsilon \leq {3n-3\over 2} $$

$\endgroup$
10
  • $\begingroup$ For greater generality, we can let $T$ be a full spanning forest (the union of spanning trees on each connected component). This still has at most $n-1$ edges (fewer if the graph is not connected) and is still a maximal acyclic subgraph. $\endgroup$ Commented Nov 3, 2017 at 16:22
  • $\begingroup$ Yes, yes, I assumed graph is connected. But if not you can proceed as you said. $\endgroup$
    – nonuser
    Commented Nov 3, 2017 at 16:28
  • $\begingroup$ @JohnWatson, when you say "Then each edge which is not in T (we have $\epsilon - n +1$ of those) must be on exactly one 3-cycle", I do not see why this is true. $\endgroup$
    – plr
    Commented Nov 3, 2017 at 18:05
  • $\begingroup$ Say we have an edge $AB$ which is on two 3-cycles, say $ABC$ and $ABD$. But then we have a 4-cycle $ADBC$. It is exactly the same argument as I had when I count the number of all possible 3-cycles. $\endgroup$
    – nonuser
    Commented Nov 3, 2017 at 18:08
  • $\begingroup$ Yes, I understand that if one is in two 3-cycles, you have a 4-cycle; but why having those edges in $T$ makes them unable to be on a 3-cycle. You can have a spanning tree with edges that belong to a cycle, can't you? I do not see the implication "edge in tree" $\rightarrow$ "edge not in cycle". $\endgroup$
    – plr
    Commented Nov 3, 2017 at 19:25

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .