Term
| What is the number of edges in a complete graph with n nodes? Why? |
|
Definition
| The number of edges in a complete graph with n nodes is n(n-1)/2. This is because, for each node there are n-1 other nodes it needs to be connected to, and hence n-1 edges arising from it. Each edge is thus associated with 2 nodes, which share the edge. Hence there are n(n-1)/2 edges. |
|
|
Term
| What is the number of edges in a cycle with n nodes? Why? |
|
Definition
| The number of edges in a cycle with n nodes is n, because, as you trace the path of the cycle, you add an edge for each added node, and n nodes are added to the first one (including the first one itself, at the very end) for an n-node cycle. |
|
|
Term
Graph G is a simple graph (undirected graph; a pair of nodes can have no more than one edge joining them). It has n nodes (vertices) and m edges.
Each node has degree 2. _____
The sum of the degrees of all the nodes is even. _____
The number of nodes with odd degree is even. _____
m >= n _____
The largest possible cycle in G (the one with the largest number of edges) has n-1 edges _____ |
|
Definition
| False, True, True, False, False |
|
|
Term
A connected graph is one in which there is a path from every node to every other. Given a positive integer n, describe a connected graph G such that the removal of a single edge results in a graph G' that is not connected.
Note: you may draw graphs G and G' but a drawing is not sufficient for full credit. You must describe the graph G for all possible n, and justify why you claim it satisfies the requirements. You will be best off considering a simple, undirected graph. |
|
Definition
| Suppose the n vertices are v1, v2, ..., vn. Then the undirected graph with edges: (v1, v2); (v2, v3); ..., (vi, vi- |
|
|
Term
| Let G be a tree. Recall that a tree is a connected acyclic graph. Suppose one adds a single edge to the tree, between some vertices, say, v and w. Is the resulting graph still a tree? Always? That is, is your answer independent of what v and w are? Why? A qualitative answer stated informally with all the necessary information is sufficient, your answer need not be mathematically formal. |
|
Definition
| The given graph G is a connected graph. That is, there exists a path between any two vertices on the graph. In particular, this means there is also a path between v and w, no matter what vertices they are. The addition of an edge from v to w creates a cycle: going from v to w along the original path, and returning to v along the added edge. Hence the resulting graph is no longer acyclic and hence no longer a tree. |
|
|
Term
|
Definition
|
|
Term
|
Definition
|
|
Term
| A circuit is also a path. |
|
Definition
|
|
Term
|
Definition
|
|
Term
| A simple circuit is also a path. |
|
Definition
|
|
Term
|
Definition
| A finite alternating sequence of adjacent vertices and edges of G |
|
|
Term
|
Definition
| A trail that does not contain a repeated vertex |
|
|
Term
|
Definition
| A closed walk that contains at least one edge and does not contain a repeated edges |
|
|
Term
|
Definition
| A walk that does not contain a repeated edge |
|
|
Term
|
Definition
| A circuit that does not have any other repeated vertex except the first and last |
|
|
