Bipartite graph properties

4 The complete bipartite graph \(K _ { 3,4 }\) connects the vertices \(\{ 2,4,6 \}\) to the vertices \(\{ 1,3,5,7 \}\).

1. How many arcs does the graph \(K _ { 3,4 }\) have?
2. Deduce how many different paths are there that pass through each of the vertices once and once only. The direction of travel of the path does not matter. The arcs are weighted with the product of the numbers at the vertices that they join.
3. (a) Use an appropriate algorithm to find a minimum spanning tree for this network.
   (b) Give the weight of the minimum spanning tree.

4 One of these graphs is isomorphic to \(\mathrm { K } _ { 2,3 }\). \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure}

1. Explain how you know that each of the other graphs is not isomorphic to \(\mathrm { K } _ { 2,3 }\). The arcs of the complete graph \(\mathrm { K } _ { 5 }\) can be partitioned as the complete bipartite graph \(\mathrm { K } _ { 2,3 }\) and a graph G.
2. Draw the graph G.
3. Explain carefully how you know that the graph \(\mathrm { K } _ { 5 }\) has thickness 2 . The following colouring algorithm can be used to determine whether a connected graph is bipartite or not. The algorithm colours each vertex of a graph in one of two colours, \(\alpha\) and \(\beta\). STEP 1 Choose a vertex and assign it colour \(\alpha\).
   STEP 2 If any vertex is adjacent to another vertex of the same colour, jump to STEP 5. Otherwise assign colour \(\beta\) to each vertex that is adjacent to a vertex with colour \(\alpha\). STEP 3 If any vertex is adjacent to another vertex of the same colour, jump to STEP 5. Otherwise assign colour \(\alpha\) to each vertex that is adjacent to a vertex with colour \(\beta\). STEP 4 Repeat STEP 2 and STEP 3 until all vertices are coloured.
   STEP 5 If there are no adjacent vertices of the same colour then the graph is bipartite. Otherwise the graph is not bipartite. STEP 6 Stop.
4. Apply this algorithm to graph A, starting with the vertex in the top left corner, to determine whether graph A is bipartite or not. A measure of the efficiency of the colouring algorithm is given by the number of passes through STEP 4.
5. Write down how many passes through STEP 4 are needed for the bipartite graph \(\mathrm { K } _ { 2,3 }\). The worst case is when the graph is a path that starts at one vertex and ends at another, having passed through each of the other vertices once.
6. What can you deduce about the efficiency of the colouring algorithm in this worst case? The colouring algorithm is used on two graphs, X and Y . It takes 10 seconds to run for graph X and 60 seconds to run for graph Y. Graph X has 1000 vertices.
7. Estimate the number of vertices in graph Y . A different algorithm has efficiency \(\mathrm { O } \left( 2 ^ { n } \right)\). This algorithm takes 10 seconds to run for graph X .
8. Explain why you would expect this algorithm to take longer than 60 seconds to run for graph Y .

5

1. How many arcs does the complete bipartite graph \(K _ { 5,5 }\) have? A subgraph of \(K _ { 5,5 }\) contains 5 arcs joining each of the elements of the set \(\{ 1,2,3,4,5 \}\) to an element in a permutation of the set \(\{ 1,2,3,4,5 \}\). Suppose that \(r\) is connected to \(p ( r )\) for \(r = 1,2,3,4,5\).
2. How many permutations would have \(p ( 1 ) \neq 1\) ?
3. Using the pigeonhole principle, show that for every permutation of \(\{ 1,2,3,4,5 \}\), the product \(\Pi _ { r = 1 } ^ { 5 } ( r - p ( r ) )\) is even (i.e. an integer multiple of 2, including 0 ).
4. Is the result in part (iii) true when the permutation is of the set \(\{ 1,2,3,4,5,6 \}\) ? Give a reason for your answer.

Find an expression for the number of edges in the complete bipartite graph, \(K_{m,n}\) Circle your answer. [1 mark] \(\frac{m}{n}\) \quad\quad \(m - n\) \quad\quad \(m + n\) \quad\quad \(mn\)