For a graph G, let f2(G) denote the largest number of vertices in a 2-regular subgraph of G. We determine the minimum of f2(G) over 3-regular n-vertex simple graphs G. To do this, we prove that every 3-regular multigraph with exactly c cut-edges has a 2-regular subgraph that omits at most max {0 , ⌊ (c- 1) / 2 ⌈} vertices. More generally, every n-vertex multigraph with maximum degree 3 and m edges has a 2-regular subgraph that omits at most max { 0 , ⌊ (3 n- 2 m+ c- 1) / 2 ⌈ } vertices. These bounds are sharp; we describe the extremal multigraphs.
Ilkyoo Choi supported by the Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education (NRF-2018R1D1A1B07043049), and also by Hankuk University of Foreign Studies Research Fund. Ringi Kim supported by the National Research Foundation of Korea (NRF) Grant funded by the Korea government (MSIT) (NRF-2018R1C1B6003786) Alexandr Kostochka supported by NSF Grants DMS1600592 and Grants 18-01-00353A and 16-01-00499 of the Russian Foundation for Basic Research. Boram Park supported by the Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Science, ICT and Future Planning (NRF-2018R1C1B6003577). Douglas B. West supported by National Natural Science Foundation of China Grant NSFC-11871439 and 111 Project, Ministry of Education, China.
