Please subscribe to the official Codeforces channel in Telegram via the link ×

How do I get a 2-3 subgraph or 3-4 subgraph? (Research question)
Difference between en4 and en5, changed 5 character(s)
Hi, I am writing my bachelor thesis and I came across a study which mentions finding a 2-3 subgraph and a 3-4 subgraph of an undirected graph as one of its subtask but it doesn't mention an algorithm to do it but it just says that it is done using DFS.↵

I couldn't really find anything useful online solving these problems.↵

A 2-3 subgraph is a subgraph where each node has degree 2 or 3 in this subgraph (we remove edges which go to nodes outside the subgraph) and our task is to find a maximal 2-3 subgraph (it doesn't have to be maxmimum in terms of size just that we can't add another node to it). A 
32-4 subgraph is just the same but with 2, 3 and 4.↵

Can anyone help by describing an algorithm or linking an article/paper?↵


  Rev. Lang. By When Δ Comment
en6 English YahiaSherif 2022-06-24 17:34:10 2 Tiny change: 'aph and a 3-4 subgrap' -> 'aph and a 2-4 subgrap'
en5 English YahiaSherif 2022-06-24 17:32:05 5
en4 English YahiaSherif 2022-06-24 16:32:40 0 (published)
en3 English YahiaSherif 2022-06-24 16:21:21 23 Tiny change: ' subgraph as o' -> ' subgraph of an undirected graph as o'
en2 English YahiaSherif 2022-06-24 16:20:49 1 Tiny change: 'se problem.\n\nA 2-3' -> 'se problems.\n\nA 2-3' (saved to drafts)
en1 English YahiaSherif 2022-06-24 16:20:18 772 Initial revision (published)