We’re rewarding the question askers & reputations are being recalculated! Read more.

All Questions

Filter by
Sorted by
Tagged with
1
vote
1answer
52 views

How to correctly describe this action, deleting an edge that “shortcut” some vertices

Haven't written a proof in years, not sure how to describe an algorithm like this ? Let us what we have a graph. like this below: 1). How to describe edge removal of{ (0, 1),(3,4), (1,2) }done in ...
1
vote
0answers
214 views

Proof that G is a Tree After DFS and BFS form the same tree T [closed]

Let G be a connected, undirected graph containing some vertex s. let's say that BFS and DFS are both run on G starting at s and that the breadth first search and depth first search ...
1
vote
3answers
67 views

Intuitive proof for a tree with n nodes, has n-1 edges

I am interested in an intuitive proof for "any binary tree with $n$ nodes has $n-1$ edges", that goes beyond proof by strong induction.
2
votes
1answer
84 views

Alternate proof of the Caro-Wei theorem for lower bounding the independence number

Let $G$ be a graph on $n$ vertices whose degree sequence is $d_1,d_2,...,d_n$. Let $\alpha(G)$ denote the size of maximum independent set of $G$, i.e., the size of a maximum subset of vertices of $G$ ...
1
vote
1answer
69 views

Proof By Contradiction - Hamiltonian Paths and Cycles

Was hoping if anyone had any way to prove the following claim using proof by contradiction Let $G = (V, E)$ be a simple graph with at least one vertex, and let $G'$ be the graph formed by adding a ...
0
votes
1answer
23 views

There could not be an edge from u to v in a DAG, if w is before v in a topological order

I am trying to prove that given a DAG. There exists a valid topological ordering that has v in front of u iff there is no path from u to v. The proof is related to the fact that reverse DFS post ...
1
vote
1answer
185 views

lower bound proof with adversary argument

We have to run a song on a Walkman, for that we need 2 full batteries. Let's say we have a mixed set of 30 batteries (15 are empty and and 15 are full) and then only way to test if the battery is full ...
1
vote
1answer
75 views

If a Triple Graph Grammar rule counts as a Mathematical Proof

I am intrigued by Triple Graph Grammars (TGG) as a potential for formal mathematical proof. Triple Graph Grammars (TGGs) are a technique for defining the correspondence between two different ...
2
votes
1answer
79 views

how to prove original intervals and canonical form of intervals have the same interval graph

According to this paper,a family of intervals is said to be canonical if the coordinates of the endpoints of the intervals are distinct integers between 1 and 2n where n is the number of intervals. ...
2
votes
0answers
135 views

Find, with proof, the number of distinct graphs with the vertex set $V = \{1, 2, \ldots,n\}$ [closed]

Let $n \in \mathbb{Z^+}$. Find, with proof, the number of distinct graphs with the vertex set $V = \{1, 2, \ldots,n\}$. We say two such graphs are distinct if one of them has an edge $(u, v)$ and the ...
1
vote
1answer
94 views

Prove that at least as many edges as vertices implies a cycle

I am EXTREMELY confused on where to start with this problem. We recently just started learning about graph theory and I don't know where to begin. Prove that in a connected graph G with $p$ ...
1
vote
1answer
412 views

How to show that two vertices in a connected component are in the same set? (bi conditional)

Show that after all edges are processed by CONNECTED-COMPONENTS, two vertices are in the same connected component if and only if they are in the same set. The CONNECTED-COMPONENTS algorithm is the ...
-1
votes
1answer
134 views

What do we mean when we say an edge (u,v) connects some component to other component in forest G = (V,A)

Let H = (V,E) be a connected, undirected graph. Let A be a subset of E. Let C = (W , F) be a connected component (tree) in the forest G = (V,A). Let (u,v) be an edge connecting C to some other ...
1
vote
2answers
2k views

Why is T not a minimum spanning tree of G?

The Problem: Let T be a tree constructed by Dijkstra's algorithm in the process of solving the single source shortest-paths problem for a weighted connected graph G.    a. True of false:...
1
vote
1answer
1k views

How to draw a graph to disprove this statement?

The Problem: Indicate whether the following statements are true or false: a. If e is a minimum-weight edge in a connected weighted graph, it must be among edges of at least one minimum ...
4
votes
1answer
153 views

Birkhoff-von Neumann theorem for bistochastic digraphs

A weighted digraph (with loops) is bistochastic, iff the weights are non-negative, for all non-sink nodes, the sum of the edge weights of the out-edges is $1$, and for all non-source nodes, the sum ...
1
vote
0answers
179 views

Maximum flow problem with non-zero lower bound

Given $G = (V,E )$ a directed graph, if $ X \subseteq V $ we write $$\begin{align*} \delta ^{+}(X) &= \{ xy\in E \mid x \in X, y\in V - X \} \\ \delta ^{-}(X) &= \delta ^{+}(V -...
0
votes
1answer
222 views

Unclear about proof for unique MST given graph G with distinct weights

http://homepages.math.uic.edu/~leon/cs-mcs401-s08/handouts/mst.pdf I have some trouble understanding the proof above. I understand that we assuming two MSTs, T and T', and an edge e that is the ...
1
vote
2answers
86 views

if (dis)proving a conjecture on graph theory can be done just by a counter example then can every (dis)proof be mapped actually to a counter-example?

Suppose we have a conjecture on graph theory that can be (dis)proved by means of a counter example, then, is it true that every alternative (dis)proof of the conjecture can be mapped to a counter ...
2
votes
1answer
136 views

Choose $n/2$ vertices and guarantee $3/4$ of edges are accounted for proof

Give a polynomial-time algorithm that finds ceil(V/2) vertices that collectively account for at least three-fourths (3/4) of the edges in an arbitrary undirected graph. The algorithm I have come up ...
7
votes
1answer
1k views

Proof of Ramsey's theorem: the number of cliques or anti cliques in a graph

Ramsey's theorem states that every graph with $n$ nodes contains either a clique or an independent set with at least $\frac{1}{2}\log_2 n$ nodes. I tried to look it up at a few places (including ...
1
vote
1answer
1k views

r-regular graph and hamiltonian path

I am having some issues proving a problem I am working on. I have been sketching out examples but the proof is not jumping out at me. Question: Let $G = (V,E)$ be an undirected $r$-regular graph (...
3
votes
2answers
2k views

Acyclic Tournament Digraphs and Hamiltonian Paths

I am studying MIT OCW lecture notes but they do not have solutions for the following problem. Directed Acyclic Tournaments In a round-robin tournament, every two distinct players play against each ...
5
votes
1answer
2k views

Simple Task-Assignment Problem

I have this simple 'assignment' problem: We have a set of agents $A = \{a_1, a_2, \dotso, a_n\}$ and set of tasks $T= \{t_1, t_2, \dotso, t_m\}$. Note that $m$ is not necessarily equal to $n$. Unlike ...
4
votes
2answers
2k views

How can I prove that a complete binary tree has $\lceil n/2 \rceil$ leaves?

Given a complete binary tree with $n$ nodes. I'm trying to prove that a complete binary tree has exactly $\lceil n/2 \rceil$ leaves. I think I can do this by induction. For $h(t)=0$, the tree is ...
7
votes
2answers
130 views

Low-degree nodes in sparse graphs

Let $G = (V,E)$ be a graph having $n$ vertices, none of which are isolated, and $n−1$ edges, where $n \geq 2$. Show that $G$ contains at least two vertices of degree one. I have tried to solve this ...
14
votes
2answers
5k views

Proving a binary tree has at most $\lceil n/2 \rceil$ leaves

I'm trying to prove that a binary tree with $n$ nodes has at most $\left\lceil \frac{n}{2} \right\rceil$ leaves. How would I go about doing this with induction? For people who were following in the ...