Given a simple graph with $n$ vertices, show that you can remove all edges in $O(n\log n)$ rounds, where in each round you are allowed to remove all edges of any (single) path.
$\begingroup$
$\endgroup$
2
-
1$\begingroup$ What have you done so far? Where did you get stuck? $\endgroup$– padawanCommented Dec 3, 2017 at 18:39
-
$\begingroup$ You might find this page helpful in improving your question. $\endgroup$– D.W. ♦Commented Dec 4, 2017 at 4:00
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
6
A classical result of Lovász (On covering of graphs) states that a graph on $n$ vertices can be decomposed into at most $n/2$ paths and cycles, and so into at most $n$ paths.
answered Dec 3, 2017 at 22:15
-
$\begingroup$ thanks but its somehow too complicated i think proving nlogn would be much easier i would appreciate if you could give me answer for nlogn thanks in advance:) $\endgroup$ Commented Dec 4, 2017 at 6:07
-
-
-
$\begingroup$ It's hard for me to guess which argument the setter is looking for without further context. $\endgroup$ Commented Dec 4, 2017 at 6:30
-
$\begingroup$ i think you're right the further context the better. thanks! $\endgroup$ Commented Dec 4, 2017 at 6:39