Excuse the poor quality image, but it illustrates my point well enough. I couldn't find the answer anywhere else online.
$\begingroup$
$\endgroup$
4
-
1$\begingroup$ By a subdivision, do you mean that you are adding a new vertex in every edge between the left and right-hand subsets? Note for instance that if you don't add in a new vertex in every edge from the previous edges from left to right, then if you try to find a bipartite subdivision of the new graph via A (new vertices) and B (old vertices), then you will have some edges among the elements of B. $\endgroup$– locally trivialCommented Apr 20, 2022 at 17:44
-
2$\begingroup$ If you subdivide every edge you get a bipartite graph regardless of what graph you started with. $\endgroup$– lambdaCommented Apr 20, 2022 at 18:45
-
$\begingroup$ @lambda I see, is there a formal proof for this? This is the first time I've actually seen this anywhere, and it's surprising to me that this isn't something that is taught. I can see that it does seem to be true, but I can't see how this would be applied in a general proof. $\endgroup$– user480911Commented Apr 21, 2022 at 1:11
-
5$\begingroup$ The "new" vertices are adjacent only to "old" vertices, and the old vertices are adjacent only to new vertices, exactly as in the diagram. $\endgroup$– Gerry MyersonCommented Apr 21, 2022 at 3:13
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
I can write up this one. It looks like the definition of subdivision of a graph $G = (V,E)$ is: for every edge $\{u,v\}$, create a new vertex $w_{u,v}$. Make a new edge $\{u,w_{u,v}\}$ and a new edge $\{v,w_{u,v}\}$. Delete the old edge $\{u,v\}$.
Let $W$ be the set of new vertices created.
The new graph must be bipartite, in fact, a partition is $(W,V)$. All the old edges in the graph have been deleted; there are only "new" edges. Every new edge has one endpoint in $W$ and one endpoint in $V$. QED.
