Answer to Question #242425 in Discrete Mathematics for yassal

Question

Draw these graphs.

a) K7 b) K1,8 c) K4,4

d) C7 e) W7 f ) Q4

Answer 1

The complete graph of n vertices, denoted by K_n , is the simple graph that contains exactly one edge between each pair of distinct vertices.

The cycle C_n($n\ge3$ ) , consists of n vertices $v_1.v_2,...,v_n$  and edges $\{v_1,v_2\},\{v_2,v_3\},...,\{v_{n-1},v_n\}=\{v_n,v_1\}$

We obtain the wheel W_n , when we add an additional vertex to the cycle C_n for $C\ge3$  and connect this new vertex to each of the n vertices in C_n , by new edges.

The n – cube, denoted by Q_n, is the graph that has vertices representing the 2ⁿ 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 K_m,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) K₇ has 7 vertices and there needs to be an edge between every pair of vertices.

b) K_1,8 has two sets of vertices: a set of 1 vertex and a set of 8 vertices

$M=\{A\}$

$N=\{B,C,D,E,F.G.H.I\}$

The vertex that is alone in its set should be connected to all other vertices.

c) K_4,4 has two sets of vertices: a set M of 4 vertices and a set N of 4 vertices

$M=\{A,B,C,D\}$

$N=\{E,F,G,H\}$

All vertices in the set M should be connected with every vertex in the set N.

d) C₇ 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) W₇ is the graph of C₇ in part (d) to which a vertex H was added and this vertex is connected with all other vertices.

f) Q₄ has 2⁴=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.