Question

Suppose we have 2n people, some of which are related to some of the others. We might want

to split them into groups of two, so that the two people in a group are related (if this is

possible).

Expressing this as a graph problem, suppose we have an undirected graph G = hV;Ei. A

pairing is a set P E of edges such that for all (u; v); (x; y) 2 P, the nodes u; v; x; y are all

different. In other words, no two edges in P have a node in common. A complete pairing is a

pairing P that uses all the graph’s nodes, that is, a pairing for which

S

(u;v)2P fu; vg = V .

Suppose we have 2n people, some of which are related to some of the others. We might want to split them into groups of two, so that the two pcople in a group are related (if this is possible). Expressing this as a graph problem, suppose we have an undirected graph G-〈ν.Ε). A pairing is a set P E of edges such that for all (u, e), (x,y) є Р. the nodes u, v, x, y are all different. In other words, no two edges in P have a node in common. A complete pairing is a pairing P that uses all the graph's nodes, that is, a pairing for whichplu,v)-V For example, in the graph shown below, one possible complete pairing is {(a, b), (d, e), (c, f) but there is no complete pairing that contains the edge (b, c) Use mathematical induction to show how to construct a graph with 2n nodes and n2 edges such that the graph has exactly one, unique, complete pairing.

Answer 1

Consider

A graph G=(V,E)

V----->set of vertices

E------->set of edges

• vertices we can call it as objects
• edges we can call it as model relationship.
• for example graph can be model a network of people and edges refers friendship
• In undirect graph , E- set of unordered pair of vertices(u,v)
• (u,v)$\varepsilon$ V

consider above graph,

V=

a, b, c,d, e, fj

E=$\left \{ (a,b),(a,d),(b,c),(b,e),(d,e),(e,c),(c,f) \right \}$

• (b,c) and (c,b) are different descriptions of same edge, because unordered sets
• graph G=(V,E) has 6 nodes and 8 edges
• complete graph on n verices

             for all x,y$\epsilon$ V(G),$\left \{ x,y \right \}$$\epsilon$ E(G)

           ----> all pairs of vertices are adjacent so that each vertex degree is (n-1)

therefore we get $\sum$ i=1 to n (n-1)=2E= n(n-1)

there are n(n-1)/2 edges

if n=2

E= 2(2-1)/2 =1 ---->true

E=k(k-1)/2

IS : E=k+1(k)/2

E = (k(k-1) +2k)/2

E= (k²-k)/ 2

E = k(k-1)/2

Mathematical induction

• if two nodes have an edge between them, at that point the degree of those two hubs must mean at generally 2n
• In the event that you expel those two hubs from the diagram, you have a chart with 2(n-1) hub and no triangles.
• in the event that you include level of those hubs a,b, and it's higher, at that point 2n, at that point there must be a node c associated with both a and b.
• suppose if it true for (n-1), that time we should get 2(n-1) hubs or nodes and at most (n-1)² lines

             now if we edit two nodes extra ,then we can not edit more than 1+2(n-1) lines to the graph

• at last we can get 1 + 2(n-1)+(n-1)²=(1+(n-1))²= n² lines