Draw these graphs. a) K7 b) K1,8 c) K4,4 d) C7 e) W7 f ) Q4
The Answer to the Question
is below this banner.
Here's the Solution to this Question
The complete graph of n vertices, denoted by Kn , is the simple graph that contains exactly one edge between each pair of distinct vertices.
The cycle Cn( ) , consists of n vertices and edges
We obtain the wheel Wn , when we add an additional vertex to the cycle Cn for and connect this new vertex to each of the n vertices in Cn , by new edges.
The n – cube, denoted by Qn, is the graph that has vertices representing the 2n bit strings of length n. two vertices are adjacent if and only if the bit strings that they represent differ in exactly one bit position.
The complete bipartite graph Km,n is the graph that has its vertex set partitioned into two subsets of m and n elements respectively. There is an edge between two vertices if and only if one vertex is in the first subset and the other vertex is in the second subset.
a) K7 has 7 vertices and there needs to be an edge between every pair of vertices.
b) K1,8 has two sets of vertices: a set of 1 vertex and a set of 8 vertices
The vertex that is alone in its set should be connected to all other vertices.
c) K4,4 has two sets of vertices: a set M of 4 vertices and a set N of 4 vertices
All vertices in the set M should be connected with every vertex in the set N.
d) C7 has 7 vertices A,B,C,D,E,F,G, where A and B are connected, B and C are connected,...,
F and G are connected, and G and A are connected.
e) W7 is the graph of C7 in part (d) to which a vertex H was added and this vertex is connected with all other vertices.
f) Q4 has 24=16 vertices, which are the bit strings of length 4: 0000, 0001, 0011, 0010, 0100,
0101, 0110, 0111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111
Two vertices are connected, if the two corresponding bit strings differ by 1 bit.