7.02d–7.02f - Complete and bipartite graphs

7.02d–7.02f - Complete and bipartite graphs

Recognise graphs containing every possible connection, and graphs whose vertices can be divided into two sets with connections only between the sets. In 7.02d7.02d you will count the arcs of a complete graph; in 7.02e7.02e you will describe complete bipartite graphs; in 7.02f7.02f you will prove or disprove bipartiteness using two colours.

Complete graphs

Six people each shake hands with every other person once. How many handshakes take place, and why does dividing people into two groups change the answer? The graph turns each handshake into one arc, so it keeps you from counting the same meeting twice.

You already know

A simple graph has no loops or multiple arcs. A vertex degree counts its incident arc ends, and the sum of all degrees is twice the number of arcs.

For three people the graph is a triangle: each vertex joins both others. Four people require all six pairs, including both diagonals of a four-vertex drawing. The crossings of those diagonals add no vertices.

[DIAGRAM: asset_name: Complete graphs on four and five vertices; asset_slug: h245_7_02_complete_graphs; caption: Every pair of distinct vertices is joined in K4 and K5; description: Two panels show labelled K4 and K5 on convex vertices, with all six and ten arcs respectively. Their degrees are labelled 3 and 4, and unmarked crossings are not vertices.]
Every pair of distinct vertices is joined in K4 and K5

Complete graph

A complete graph is a simple graph in which every pair of distinct vertices is adjacent. The complete graph on nn vertices is written KnK_n. Every vertex of KnK_n has degree n−1n-1. The notation and definition are not supplied in the formula booklet.

There are nn degrees of n−1n-1, but their sum counts each arc at both ends.

Arcs in a complete graph

For KnK_n,

E=n(n−1)2E=\frac{n(n-1)}{2}

Not in the formula booklet: learn it.

Count each unordered pair once, whether the drawing is easy or impossible to read.

Worked example 1: counting handshakes

Question. Six people each shake hands once with every other person. Find the number of handshakes.

Plan. Model the people as K6K_6 and count its arcs.

deg⁡v=6−1=5each person meets five othersE=6×52=15each handshake has two ends\begin{aligned} \deg v&=6-1=5 && \text{each person meets five others}\\ E&=\frac{6\times5}{2}=15 && \text{each handshake has two ends} \end{aligned}

Why this step? Multiplying six by five counts each handshake twice, once from each participant.

Answer. There are 1515 handshakes.

Check. Count new partners person by person: 5+4+3+2+1=155+4+3+2+1=15.

The second example changes only what is known: the arc count is supplied and the number of vertices must be recovered.

Worked example 2: recovering the vertex count

Question. A complete graph has 2828 arcs. Determine the number of vertices.

Plan. Set the complete-graph formula equal to 2828, then keep the positive integer solution.

n(n−1)2=28complete graphn2−n−56=0multiply by two and rearrange(n−8)(n+7)=0factorisen=8a vertex count is positive\begin{aligned} \frac{n(n-1)}{2}&=28 && \text{complete graph}\\ n^2-n-56&=0 && \text{multiply by two and rearrange}\\ (n-8)(n+7)&=0 && \text{factorise}\\ n&=8 && \text{a vertex count is positive} \end{aligned}

Why this step? The quadratic's negative root is algebraically valid but cannot count vertices.

Answer. The graph has 88 vertices.

Check. K8K_8 has 8×7/2=288\times7/2=28 arcs.

Completeness is a condition on every pair of vertices; a high degree at just one vertex is insufficient.

Watch out

Wrong: “A graph on five vertices with a vertex of degree four is K5K_5.” That one vertex joins all the others, but the other pairs may be missing. Every vertex must have degree four in a simple graph on five vertices for the graph to be K5K_5.

Recover a different complete graph from its arc count.

Bipartite graphs

Suppose three tutors can teach four pupils, but tutors do not tutor one another and pupils do not tutor one another. The connections naturally run between two sets. Some tutor-pupil pairs may be absent; the two-set restriction still makes sense.

Bipartite graph

A graph is bipartite if its vertex set can be divided into two disjoint sets so that every arc has one end in each set. There are no arcs joining two vertices within either set. The sets need not have equal sizes, and not every cross-set pair has to be joined.

For example, the graph with arcs AB,BC,CDAB, BC, CD is bipartite with sets {A,C}\{A,C\} and {B,D}\{B,D\}. The two sets are descriptions of connections, not necessarily groups that were specified in the story. An isolated vertex can go into either set. The definition is not supplied in the formula booklet.

A triangle is a useful non-example. Put AA in the first set. Its two neighbours BB and CC must both go in the second set, but the arc BCBC would then join two vertices within that set. So a triangle is not bipartite.

Key idea

Bipartite means that a valid two-set division exists. Complete bipartite adds the requirement that every possible connection between the sets is present.

A drawing with two visible columns is not evidence on its own: inspect every connection.

Complete bipartite graphs

When every object in one set connects to every object in the other, you can count connections without drawing each one.

[DIAGRAM: asset_name: The complete bipartite graph K3,4; asset_slug: h245_7_02_complete_bipartite; caption: K3,4 has seven vertices and twelve arcs, all joining the two sets; description: Three blue vertices A B C lie in the left column and four sage vertices P Q R S in the right column. All twelve cross-set arcs are drawn. There are no within-column arcs. Labels show degree 4 at each left vertex and degree 3 at each right vertex.]
K3,4 has seven vertices and twelve arcs, all joining the two sets

Complete bipartite graph

The complete bipartite graph Km,nK_{m,n} has two disjoint sets containing mm and nn vertices, with every vertex in one set adjacent to every vertex in the other and no arcs within either set. Its degrees are nn at the mm vertices and mm at the nn vertices. This definition is not supplied in the formula booklet.

Continue this lesson.

You’re previewing NovaLearn without an account. Create a free account to read the rest.

Create free account