# Tagged Questions

23 views

### Prove that every subgraph of forest has at least one vertex of degree < 2

So I know that a forest is a graph that has no cycles. This is what I had in mind: Assume that we have the subgraph T, which has two options: to be connected or not. if it's connected it has to be a ...
18 views

### Minimum k-spanning tree including a given node

Given a Graph (V, E), it is very easy to find the minimum spanning tree using Kruskal's Algorithm. A k-minimum spanning tree is restricted to k nodes, and finding it is actually NP-hard. However, ...
73 views

### Prove that the dual graph of any (planar) graph is connected

I'd like to know if there's a standard proof that the dual graph of any planar graph is connected (or, if there's a counterexample, I'd like to know that too). I've thought of a proof that might work ...
26 views

### Show that if the diameter of an undirected graph is $d$ then there exists some vertex separator $S\subseteq V$ of size $|S| \leq { n\over d-1}$

Show that if the diameter of an undirected graph is $d$ then there is some set $S\subseteq V$ with $|S| \leq \frac{n}{d-1}$ such that removing the vertices in S from the graph would break it into ...
61 views

63 views

### $R\subset S\times S$ for $S=\{1,2,3\}$: A Graph-Theoretic Approach

So I am given the relation $R=\{(1,1),(2,2),(3,3),(1,2),(1,3)\}$ and asked which of the properties reflexive, symmetric, or transitive are held in the relation, but what I am thinking is that this can ...
1k views

### Solving graph theory proofs

I am trying to study for an exam on graph theory and I have a few questions. How would you start a proof? For example, when I see a problem like this: Let G be a graph with n vertices where every ...
81 views

### how to prove a result

I was studying about graph operation on wiki. Corona product of graphs $G_1$ and $G_2$, is the graph which is the disjoint union of one copy of $G_1$ and $|V_1|$ copies of $G_2$ ($|V_1|$ is the number ...
345 views

### Dijkstra's Shortest-Path Algorithm

I'm presented with the following algorithm: Dijkstra's Shortest-Path Algorithm This algorithm finds the length of a shortest path from veftex $a$ to vertex $z$ in a connected, weighted ...
### Show that if $n\geq 3$, the complete graph on $n$ vertices $K_n$ contains a Hamiltonian cycle.
I'm asked the following quesiton: Show that if $n\geq 3$, the complete graph on $n$ vertices $K_n$ contains a Hamiltonian cycle. This seems obvious since $K_n$ contains a subgraph which is a ...