Use this tag for questions in graph theory. Here a graph is a collection of vertices and connecting edges. Use (graphing-functions) instead if your question is about graphing or plotting functions.

learn more… | top users | synonyms

2
votes
2answers
244 views

Graph Run Time, Nodes and edges.

Hi i have these two problems that are part of a practice set i am doing for exams, i can't seem to get around them. If you can answer any of them thanks in advance. For a given graph $G=(V,E)$ and ...
2
votes
1answer
120 views

Why is the number of vertices in a graph $\geq n_0(d,g)$?

(Reinhard Diestel Graph Theory, GTM 173, edition 3) Theorem 1.3.4 (Alon, Hoory, Linial 2002): Let $G$ be a graph. If $d(G) \geq d \geq 2$ and $g(G) \geq g \in \mathbb N$, then $|G| \geq n_0(d,g)$, ...
2
votes
1answer
41 views

Showing a certain class of graphs has minimum degree at most 4

I found the following question in a previously assigned graph theory final: Let $G$ be a simple, planar graph with $1\leq |E(G)|< 30$. Show that $G$ has a vertex with degree at most 4. My ...
1
vote
1answer
84 views

Is an abstract simplicial complex a quiver?

Let $\Delta$ be an abstract simplicial complex. Then for $B\in \Delta$ and $A\subseteq B$ we have that $A\in\Delta$. If we define $V$ to be the set of faces of $\Delta$, construct a directed edge from ...
3
votes
1answer
112 views

Given a line graph $L(G)$, is it possible to determine whether $G$ is bipartite?

Suppose I am given a line graph $L(G)$, but don't know $G$. Is it possible for me to determine from this information whether $G$ is bipartite?
1
vote
1answer
78 views

What set of graphs can be drawn on a plane such that no edges intersect?

It's seems like all acyclic graphs can, but not all cyclic graphs (I.e. The fully connected 4 node graph can, but the fully connected 5 node graph cannot) Also, is there a name for this property? ...
5
votes
0answers
97 views

What is special about simplices, circles, paths and cubes?

There are some ubiquitous families of graphs — the complete graphs (or simplices) $K_n$, the circle graphs $C_n$, the path graphs $P_n$, and the hypercube graphs $Q_n$ — that intuitively ...
1
vote
2answers
1k views

How many edges are in a clique of n vertices? [duplicate]

I believe the answer is $\frac12(n-1)^2$, but I couldn't confirm by googling, and I'm not confident in my ability to derive the formula myself.
3
votes
2answers
149 views

Absolute difference between incoming and outgoing edges.

I am trying to prove that an algorithm can be devised to guarantee that absolute value of the difference between the sum of incoming edges and outgoing edges for each vertex is less than or equal to ...
1
vote
0answers
65 views

Finding the minimum length of an addition chain

It is known that for every positive integer $n$ there exists one or more optimal addition chains of minimum length. It is rumored that finding the length of the optimal chain is NP-hard, and the ...
2
votes
1answer
77 views

Conditional merge of a sequence of DAGs / partial orders

I have a sequence of directed acyclic graphs, $G_i$. The union of their edge sets may not be a DAG. I want to find an edge set that is maximal in some sense but still acyclic. Alternatively I have a ...
-1
votes
1answer
78 views

Confusion about the definition of graphs

From this graph theory lesson : A graph is a non-empty finite set $V$ of elements called vertices together with a possibly empty set $E$ of pairs of vertices called edges. Here are a few ...
5
votes
2answers
237 views

question about simple graph.

I know that simple graph has no parellel edges and loops. My question is that I have to draw the graph on six vertices with degree sequence $(3,3,5,5,5,5)$. I draw the the graph with the given degree ...
4
votes
2answers
161 views

Gentle introduction into stability and classification theory

I am badly looking for a (very) gentle introduction into stability and classification theory answering at least some of the following questions: Why is a stable theory called "stable"? What is a ...
0
votes
1answer
334 views

Network flow: Why is min-cut determined by unsaturated edges?

Suppose we have an oriented graph and max-flow has been determined. I found that to determine min-cut or minimum s-t cut can then be found by labeling graph nodes such that nodes belonging to source ...
0
votes
1answer
208 views

A problem on the friends and strangers theorem

There is a group of 20 people. Each pair of people are either friends or strangers, and each person finds exactly 6 strangers in the group. If all possible committees of 3 are formed from the group, ...
3
votes
2answers
323 views

Removing degree-2 vertices from a graph

Consider a map of a river system. Each point on the river line is a graph vertex. Some points have degree 1, at the start and end of a river, some have degree > 2 where rivers merge (or more rarely, ...
4
votes
1answer
167 views

Eigenvalues of a special block matrix associated with strongly connected graph

Definition Let $G=(V,E,A)$ be a strongly connected directed graph, where $V=\{1,2,...,n\}$ denotes the vertex set, $E$ is the edge set, and $A$ is the associated adjacent matrix with $0-1$ weighting, ...
3
votes
1answer
699 views

Finding the virtual center of a cloud of points.

Given: (latitude, longitude) points $P_1, P_2,\ldots, P_n$. Presumably, all the points should form a dense cloud. However, noise is possible. Needed: The virtual center of the points. For ...
0
votes
2answers
485 views

graph theory and forests

We were given an this question in my class: Prove that a forest with n vertices and m components has n-m edges using induction on m. Induction is not my strongest point and I was wondering if anyone ...
4
votes
0answers
319 views

Combinatorial problem on subgraphs of the Johnson graph

The following problem emerged from my project about distributed computing. First some definitions: Let $1\leqslant m \leqslant n$, $N=\{ 1,\ldots,n\}$. The Johnson graph $J_{n,m}$ has as vertex set ...
3
votes
0answers
127 views

undirected random graph: common neighbors between two vertices

I have a undirected random graph with node degree distribution $P(k)$, I pick a random vertex $v_0$ and I randomly select a neighbor $v_1$ (the selection is made with uniform probability). What is ...
3
votes
1answer
104 views

What can we prove with infinite graphs that we cannot prove without them?

I asked the following question on CSTheory.SE and was advised that this site might be a more appropriate place for it. Below the line you find the slightly edited question, the original one is here. ...
2
votes
1answer
127 views

Boolean circuits and digraphs

It is well known that connecting NAND gates allows the construction of arbitrary circuits. Furthermore, a NAND gate can be represented as a digraph with four vertices (in order, the two inputs, the ...
0
votes
1answer
759 views

Hamiltonian Cycle Problem

At the moment I'm trying to prove the statement: $K_n$ is an edge disjoint union of Hamiltonian cycles when $n$ is odd. ($K_n$ is the complete graph with $n$ vertices) So far, I think I've come ...
2
votes
0answers
49 views

Partitioning a graph G into at most O(n/k) connected clusters of radius at most k.

Prove that every unweighted n-vertex graph G and every integer k>=1, there exists a partition of G into at most O(n/k) connected clusters of radius at most k. I dont even have a clue on how to strike ...
1
vote
1answer
849 views

Graph where all nodes are pivotal

I am reading a text for an upcoming class Social Network Analysis on Corsera.org and am trying to get a little bit ahead by reading some of the material before class starts. I am working on a question ...
2
votes
0answers
49 views

The effect op graph operations on the chromatic number (Papers/Books)

Can anyone please direct me to a paper or even a textbook which would provide a good read on how graph operations influence the chromatic number of a graph? Thanks.
2
votes
1answer
282 views

Number of sinks/sources in a a random directed acyclic graph

Given an arbitrary graph $G = (V,E)$, such that each vertex v is given randomly a unique integer identifier (call it v). An edge (u,v) is directed from u to v if u > v. This creates a DAG. A ...
-2
votes
1answer
120 views

A Graph Theory Problem

Define $P(S)$ as $$\exists a, b \in S (a - b \in S).$$ Prove that for any subset $S$ of $A = \{1, 2, 3, 4, 5\}$, $P(S)$ or $P(A - S)$ holds. Please prove it using some graph theory.
2
votes
2answers
72 views

Decomposition of graph

Prove that if $G$ is a graph with degree of every vertex at most $3$, then it can be decomposed for graphs $C,T$, where $C$ is a sum of vertex-disjoint cycles and $T$ is a sum of trees. I ...
4
votes
1answer
101 views

Graph for which certain induced subgraphs are cycles

Let us call a graph G $nice$ if for any vertex $v \in G$, the induced subgraph on the vertices adjacent to $v$ is exactly a cycle. Is there anything that we can conclude about nice graphs? In ...
1
vote
1answer
534 views

Strongly connected directed clique, Hamiltonian cycle

Let $G$ be a directed clique. Prove that $$G \text{ has Hamiltonian cycle} \Leftrightarrow G\text{ is strongly connected}$$ $(\Rightarrow)$ is obvious, but I completely don't know how to prove ...
0
votes
1answer
225 views

Explanation of Unweighted Shortest path definition from Introduction to Algorithms by Cormen et al

From Introduction to Algorithms by Cormen et al: We are given a directed graph G = (V,E) and vertices ${u,v}\in V $ and then the define Unweighted shortest path to ...
0
votes
1answer
581 views

What is a subproblem graph in dynamic programming parlance?

I know what dynamic programming is but I do not really understand the concept of subproblem graph for a dynamic programming ? How are they useful ? When solving problem by dynamic programming should ...
1
vote
4answers
2k views

What is the definition of an weighted graph?

In graph theory which one of these two will be called a weighted graph ? A graph where vertices have some weights or vales . A graph where edges have some weights or values . A graph where both ...
1
vote
1answer
56 views

Graph properties characterized by finitely many 'simplest examples'

Recently I heard someone talking about a general result saying that a graph property satisfying certain conditions always is characterizable via a (finite) set of 'smallest examples' (similar to the ...
4
votes
2answers
74 views

Is the cycle graph $C_n$ defined only for $n \ge 3$?

I'm having a hard time seeing what $C_n$ would be for $n = 1$, or $n = 2$. Can someone clear up my confusion?
8
votes
4answers
5k views

Graph theory: adjacency vs incident

Okay, so I think if 2 vertices are adjacent to each other, they are incident to each other....or do I have it wrong? Is this just different terminology. I thought I was totally clear on this for my ...
9
votes
1answer
495 views

What is the significance of the graph isomorphism problem?

It seems that graph isomorphism is an overwhelmingly interesting problem, particularly computationally. Why is that? What are the (theoretical and practical) implication of the existence of an ...
3
votes
2answers
249 views

Smallest Planar Cubic Graph with Non Hamiltonian Edge

I'm looking for the smallest simple planar cubic hamiltonian graph without triangles and with at least one edge that never lies on a hamiltonian cycle. I've got one with triangles ...
7
votes
1answer
820 views

Proof for Heine Borel theorem

I am trying to prove the Heine Borel theorem for compactness of the closed interval $[0,1]$ using Konig's lemma. This is what I have so far: I assume $[0,1]$ can be covered by ...
1
vote
1answer
602 views

Consider a graph G such that at least one vertex v is connected to all other vertices. Prove that G is not bipartite.

Consider a graph G such that at least one vertex v is connected to all other vertices. Prove that G is not bipartite. That's the question, however, I don't think it can be proven. I think there's ...
4
votes
1answer
152 views

Chess tournament, graph

Problem. In chess tournament each player, from all $n$ players, played one game with every another player. Prove that it is possible to number all players with numbers from $1$ to $n$ in such way ...
2
votes
2answers
243 views

For graph $G$, vertices $s,t$ find the shortest path between $s$ and $t$ by weight among all the shortest paths by edges

Given directed graph $G=(V,E)$, two vertices and a weights function $w: E \to R$. In addition we know that there aren't negative cycles in $G$. I need to find a linear algorithm that finds among the ...
1
vote
1answer
131 views

Max flow in a flow network such that $e \in E$ has the maximum flow it can have.

Given a flow network $G=(V,E)$, source $s$ , sink $t$ and capacity function $c:E \to \mathbb{R}^+ \cup \{0\}$ ; as well an edge $e=(u,v) \in E$. I need to find an efficient algorithm which finds among ...
2
votes
2answers
237 views

Shortest paths from $s$ by weight which contain even number of edges

Given a directed graph $G=(V,E)$, and a vertex $s\in V$, for every edge there's an integer weight $w(e)$ (positive or negative), I need to find an algorithm such that for every vertex $v \in V$ it ...
0
votes
1answer
81 views

finding two trees from a graph

The problem is related to check existence of 2 trees of a graph such that: 1)vertices in 2 trees are disjoint and no vertices are missed 2)Any tree edge cannot be a graph edge of original graph. I ...
1
vote
1answer
79 views

What type of graph problem is this?

Lets say I have four group A [ 0, 4, 9] B [ 2, 6, 11] C [ 3, 8, 13] D [ 7, 12 ] Now I need a number from each group(i.e a new group) E [num in A,num in B, num in C, num in D], such that the ...
2
votes
0answers
76 views

Ramsey (graph) theory question with tree and girth

Sorry for the abundance of questions I'm asking. Test is soon... Prove that for every tree $T$ and every $g \in \mathbb{N}$, exist $G$ with girth $g$, so that in any 2-edge-coloring of $G$ there is a ...