Solution to Draw these graphs. a) K7 b) K1,8 c) K4,4 d) C7 e) W7 f ) … - Sikademy
Author Image

Archangel Macsika

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.

Can't find a solution anywhere?


Get the Answers Now!

You will get a detailed answer to your question or assignment in the shortest time possible.

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(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 Wn , when we add an additional vertex to the cycle Cn for C\ge3  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) Qhas 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.

Related Answers

Was this answer helpful?

Join our Community to stay in the know

Get updates for similar and other helpful Answers

Question ID: mtid-5-stid-8-sqid-1487-qpid-1225