Find a 3 regular graph M such that graph H of Figure 216 is

Find a 3- regular graph M such that graph H of Figure 2.16 is an induced subgraph of M. Prove that it is impossible to find such an M that has just two vertices more than H has. 18. Show that a graph with n vertices and k edges such that k

Solution

Solution : 17 )

1 ). Let G = < V, E > be a graph. H = < V\' , E\' > is a subgraph of G if G\' is a graph, V\' V and E\' E. V\' is an induced subgraph if E\' = E P2(V\' ). Finally, it is a spanning subgraph if V\' = V.

A labelled graph G = < V, E > has 2^|V| induced subgraphs, one for each subset of its vertex set, and 2^|E| spanning subgraphs, one for each subset of its edge set.

2 ). Let M = < V, E >, such that V = {a, b, c, d, e, f}

and

E = {{a, b}, {a, c}, {b, c}, {a, d}, {d, e}, {d, f}, {e, f}, {b, e}, {c, f}}. It is obvious that H is an induced subgraph of M. M could not possibly have only one additional vertex because that vertex would have degree 3 whereas H lacks at least four edges, one incident with each of b, c and two incident with d.