Graph types, subgraphs, connection models and method selection

Simple graphs and overlapping properties

A simple graph has no loops or parallel edges. An isolated vertex has degree zero. An edgeless graph has no edges, but may still have vertices; the older practice calls this degenerate. These descriptions are not always exclusive. A complete simple graph Kₙ joins every pair of distinct vertices once

1. 1Simple graph No loops and at most one edge between each pair of distinct vertices
2. 2Subgraph Its vertices come from the parent, and every retained edge has both endpoints retained. It may omit edges as well as vertices
3. 3Complete graph Every pair of distinct vertices is joined once. The one-vertex graph is complete without needing a loop
4. 4Do not confuse overlap with contradiction A complete graph is simple. A simple graph can also have isolated vertices. State the property being tested

Subgraphs need both vertex and edge membership

For a subgraph H of G, every H vertex is a G vertex and every H edge is a G edge, with its endpoints retained in H. It is not necessary to retain all edges between the chosen vertices: that stronger requirement defines an induced subgraph. A spanning subgraph instead retains all parent vertices

In a graph model of objects and direct connections, which assignment comes first?

Graph models and structure

A graph model separates the objects from the direct connections between them. Structural checks can then count vertices and edges, test subgraph membership, or count the pairs in a complete graph

1. 1Objects are vertices Use one vertex for each object or location in the model \(\displaystyle \text{objects}\longrightarrow V\)
2. 2Direct connections are edges Use an edge to represent each stated direct connection between two vertices \(\displaystyle AB\in E\)
3. 3A subgraph uses parent elements A subgraph may omit vertices or edges, but it cannot add an element that is absent from the parent \(\displaystyle V'\subseteq V,\quad E'\subseteq E\)
4. 4Complete graphs use unordered pairs A complete simple graph has one edge for each unordered pair of distinct vertices \(\displaystyle K_6:\;\frac{6(6-1)}{2}=15\)

A complete simple graph has 6 vertices. Find its total number of edges

A simple graph has 6 vertices and 9 edges. How many additional edges make it complete?

Swapping graph roles. One of these lines is right. Which one?

G has vertices A, B, C, D and edges AB, BC, CA, CD. Which listed graph is a subgraph of G?