Four-dimensional CT scans provides valuable motion information of patient throughout different respiratory phases. PET, on the other hand, provides functional information about tumor, which differentiate tumor from normal tissue effectively. However, manually contouring structures of interest on 4D CT is prohibitively tedious due to the large amount of data. In this paper, we propose an automatic method to segment lung tumor simultaneously for 4D CT scans in all phases and PET scan. The problem is modeled as an optimization problem based on Markov Random Fields (MRF) which involves region, boundary terms and a regularization term between PET and CT scans. The problem is solved optimally by computing a single max flow in a properly constructed graph. As far as the authors know, this is the first work in simultaneously segmenting tumor in 4D CT while incorporating PET information. Experiments on 3 lung cancer patients are conducted. The average Dice coefficient is improved from 0.680 to 0.791 compared to segmenting tumor volume in 4D CT phase by phase without incorporating PET information. The proposed method is efficient in terms of running time since the method only requires computing a max flow for which efficient algorithm exists. The memory consumption is linearly scalable with respect to number of 4D CT phases, which enables our method to handle multiple 4D CT phases with reasonable memory consumption.