# Can every undirected graph be transformed into an equivalent graph (for the purposes of path-finding) with a maximum degree of 3 in logspace?

Can every undirected graph be transformed into an equivalent graph (for the purposes of path-finding) with a maximum degree of 3 in logspace?

Given an undirected graph G, is there another graph, H, such that:

• all vertices of G are in H
• H is allowed extra vertices not in G
• if a and b are connected in G, a and b are also connected in in H (possibly with at least some of the extra vertices in the H path from a to b)
• if c and d are not connected in G, c and d are not connected in H
• each vertex in H has degree at most 3
• the edges of H can be enumerated in logspace given an input G

Maybe this could be called a logspace reduction of G to a graph that has max degree of 3 that preserves connectivity?

For each edge $$(u,v)$$ in $$G$$, add vertices $$w_{u,v}$$ and $$w_{v,u}$$ to $$H$$, and add the edge $$(w_{u,v},w_{v,u})$$ to $$H$$.
For each vertex $$u$$ in $$G$$, if $$u$$ has edges $$(u,v_1),\dots,(u,v_k)$$, then add edges $$(w_{u,v_i},w_{u,v_{i+1}})$$ and $$(u,w_{u,v_1})$$ to $$H$$; and add edges $$(w_{v_i,u},w_{v_{i+1},u})$$ and $$(w_{v_1,u},v)$$ to $$H$$.
I believe this $$H$$ satisfies all of your properties. Also, I believe it can be constructed in logspace (please check me and verify for yourself).