 |
| ||
| |||
|
| Math Central | Quandaries & Queries |
|
Question from a student: Suppose that G be a bipartite graph with maximum degree of k. Prove that: 1)Exists a K-regular bipartite graph that G be subgraph it(H) |
Hi,
If the minimum degree of G is also k, then G is itself k-regular.
Otherwise, make two copies G', G'' of G, and for every vertex u of G of degree less than k, join its copy u' in G' to its copy u'' in G''.
Prove that the resulting graph is bipartite, and that its minimum degree is one more than that of G. Do you see how that helps?
Claude
| ||
| ||
| ||
 |
 |
|
Math Central is supported by the University of Regina and The Pacific Institute for the Mathematical Sciences.