Definitions
Graph, vertex, edge, degree, isomorphism and subgraph, established by asking which of several drawings represent the same graph.
3 exercises
Exercise 1
If 10 people each shake hands with each other, how many handshakes took place? What does this question have to do with graph theory?
Exercise 2
Among a group of 5 people, is it possible for everyone to be friends with exactly 2 of the people in the group? What about 3 of the people in the group?
Exercise 10
Decide whether the statements below about subgraphs are true or false. For those that are true, briefly explain why (1 or 2 sentences). For any that are false, give a counterexample.
Any subgraph of a complete graph is also complete.
Any induced subgraph of a complete graph is also complete.
Any subgraph of a bipartite graph is bipartite.
Any subgraph of a tree is a tree.
Adapted from Discrete Mathematics: An Open Introduction © 2013–2019 Oscar Levin. Licensed under CC BY-SA 4.0. Source: Discrete Mathematics: An Open Introduction. Imported at revision 1e2e26b.