Graph families and tree conditions

Complement means the missing distinct pairs

A complement is defined here for a simple graph on a fixed vertex set. Keep every vertex, including isolated vertices. Between each pair of distinct vertices, put an edge exactly when the original has none. Do not create loops. Applying this operation twice restores the original graph

1. 1Complement on a fixed set Keep every vertex of a simple graph. Join distinct vertices exactly when they were not joined in the original
2. 2Complement degrees For n vertices, each vertex has n−1 possible neighbours; original degree plus complement degree is n−1 \(\displaystyle \deg_G(v)+\deg_{\overline G}(v)=n-1\)

G has four vertices A, B, C, D and edges AB and BC. Of the six distinct vertex pairs, how many are edges of its complement?

Written complement construction (ungraded)

On paper, draw the complement of the simple graph with vertex set {A,B,C,D} and edge set {AB,BC}. Keep D even though it is isolated in the original. Label all vertices and list every complement edge. This independent construction is not automatically marked

Model complement construction

The six possible pairs are AB, AC, AD, BC, BD and CD. Removing the original pairs AB and BC leaves AC, AD, BD and CD. Draw those four edges on the same four vertices, with no loops. The following supplied diagram is a model to check against your drawing, not an automatic assessment of it

In the supplied complement model, why is D still present?

Complement boundary cases

The complement of Kₙ is an edgeless graph on the same n vertices, not an empty vertex set. The complement of an edgeless n-vertex graph is Kₙ. In particular K₁ is its own complement. For each vertex the original and complement neighbours partition the other n−1 vertices, proving the degree relation

A bipartition is not a component split

A graph is bipartite if its vertices can be divided into two disjoint classes with every edge crossing between classes. The classes cover all vertices. A connected graph can be bipartite, and disconnected graphs can be bipartite. Isolated vertices can go in either class. The definition does not require all cross-pairs to be joined

1. 1Bipartition Split the whole vertex set into two disjoint classes so every edge crosses. Within-class edges are forbidden; some cross-pairs may be absent
2. 2Complete bipartite A complete bipartite graph with class sizes m and n has every cross-pair joined, giving mn edges

The path P-Q-R-S is shown. Which statement describes it correctly?

Complete bipartite graphs

For a complete bipartite graph with classes of sizes m and n, every one of the m vertices in one class is joined to all n vertices in the other, and no within-class pairs are joined. Counting from the first class gives m times n distinct edges. K₂,₃ has five vertices and six edges; its degrees are three at the two first-class vertices and two at the other three. It is not regular, though K₃,₃ is regular of degree three

Why an odd cycle prevents bipartiteness

As you move along an edge in a bipartite graph you change class. Around a cycle you return to the starting vertex and hence its class. An odd number of changes ends in the other class, a contradiction. Therefore no bipartite graph contains an odd cycle. A triangle is the smallest example; even cycles can alternate classes

A graph contains a triangle, even if other vertices and edges are attached. What follows?

Regular does not mean complete or connected

A graph is r-regular when every vertex has degree r. A cycle is 2-regular; two separate cycles are also 2-regular. An edgeless graph is 0-regular. Regularity does not imply that every vertex is joined to every other one. In a simple r-regular graph on n vertices, the complement is (n−1−r)-regular by the proved degree relation

A simple 3-regular graph has eight vertices. What is its complement degree?

The five Platonic graphs

Take the vertices and edges of a regular convex solid, ignoring its faces as graph elements. The five Platonic graphs are tetrahedral, cube, octahedral, dodecahedral and icosahedral. Their regular degrees and vertex/edge totals are listed next. This is a graph representation of each solid, not a demand to build a 3D model or prove the classification of regular solids

Platonic graph data

In each row the degree sum equals twice the edge count. Equal edge counts do not establish isomorphism

1. 1Tetrahedral 4 vertices; 6 edges; degree 3
2. 2Cube 8 vertices; 12 edges; degree 3
3. 3Octahedral 6 vertices; 12 edges; degree 4
4. 4Dodecahedral 20 vertices; 30 edges; degree 3
5. 5Icosahedral 12 vertices; 30 edges; degree 5

The supplied tetrahedral graph is a drawing: unmarked edge crossings are not vertices. Which description matches its vertex and degree data?

The supplied cube graph is a drawing: unmarked edge crossings are not vertices. Which description matches its vertex and degree data?

The supplied octahedral graph is a drawing: unmarked edge crossings are not vertices. Which description matches its vertex and degree data?

The supplied dodecahedral graph is a drawing: unmarked edge crossings are not vertices. Which description matches its vertex and degree data?

The supplied icosahedral graph is a drawing: unmarked edge crossings are not vertices. Which description matches its vertex and degree data?

The cube graph has eight vertices and twelve edges; the octahedral graph has six vertices and twelve edges. Why are they not isomorphic?