- Show that
has
vertices and
edges.
- How many 4-cycles are in
- Does
contain any copies of
?
- Show that every graph X contains a bipartite subgraph with at least half the number of edges of X?
- Let X be a graph in which every vertex has even degree. Show that it is possible to orient the edges of X such that the indegree equals the outdegree for each vertex.
- Show that a graph X is connected if and only if for any partition of its vertex set into two non-empty sets, there exists at least one edge between the two sets.
- Show that in a connected graph any two paths of maximum length have at least one common vertex.
- Let X be a graph with n vertices and e edges. Show that there exists at least one edge uv such that
- If X is a graph on n vertices containing no
‘s then the number of edges of X is less than or equal to
edges. Give an example of a graph on n vertices containing no
‘s with
edges.
More later,
Nalin Pithwa