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

1
vote
0answers
21 views

Graph Relatives for Tessellation of the Hyperbolic Plane

I'm trying to get into the theory about the Moduar group. Among the "Paracompact hyperbolic uniform tilings in [∞,3] family" in the section "Tessellation of the hyperbolic plane" I found the Order-3 ...
1
vote
1answer
30 views

What are the cycles in this graph, and what are their sizes?

I have the following graph $G$. I'd like to find how many cycles there are and what their sizes are. Please correct me if I am wrong: in this graph there are $2$ cycles, $\text{1-2-3-4-5-1}$ with ...
4
votes
2answers
13 views

Prove that the path between two nodes is unique if the graph is a tree.

I think that the proof is easy assuming that there are at least two paths between any two nodes. If that is true then there must be a cycle somewhere. But if there is a cycle then this is not a tree, ...
0
votes
1answer
25 views

Good resources on chemical graph theory

Are there some good resources on chemical graph theory, mainly some covering even the recent results (past 2000)? Tnaks in advance for any help.
1
vote
1answer
41 views

Proving that between each pair of vertices there is a path length $2$ at most

Let $G=(V,E)$ be a graph with $n$ vertices such that $\forall v,w\in V$ that doesn't have a common edge we have: $\text{deg}(v)+\text{deg}(w)\ge n-1$. Prove that for each pair of vertices ...
1
vote
2answers
38 views

How many trees does a forest with n vertices and m edges contain?

Concerning trees in graph theory: How many trees does a forest with $n$ vertices and $m$ edges contain? This has to do with combinatorics apparently but I'm struggling with these assignments ...
1
vote
1answer
129 views

How to prove it's possible to place $8$ non-attacking rooks on a chessboard with $7$ cells cut out?

From the 8 × 8 chessboard 7 cells were cut out. Prove that you can put 8 rooks to this board so that none of them can capture another rook.
0
votes
1answer
34 views

If $G$ is simple and $deg_+(v) \ge k\ge 1$ , then there is a simple cycle of at least size $k+1$

I am going to show you my proof/ and please correct me if wrong: Begin with some node $v$, and mark it. Follow one of its outgoing edge $(v,w)$ to next unmarked node, and mark it, by doing this ...
0
votes
1answer
28 views

In a complete graph of 30 nodes, what is the smallest number of edges that must be removed to be a planar graph?

I know that a planar graph can not shrink in a $K_{3,3}$ (bipartite graph with $6$ vertices) or a graph $K_5$, and also can not contain cycles of length $3$. There is a theorem that in a graph is ...
1
vote
0answers
16 views

Minimum Bound on {0,1,*} Address Length of Graph

Need help understanding some steps in Theorem 9.1 from Wilson and Lint: To address a graph, G - Assign every vertex of G an element from $\{0,1,*\}^n$ such that the distance between 2 vertices is the ...
4
votes
1answer
51 views

Partition graph into disjoint beams

Given an undirected graph such that each vertex has degree exactly $100$. A beam is a set of $10$ edges connected to the same vertex. Prove that the set of all edges can be partitioned into disjoint ...
1
vote
1answer
29 views

Does the Gale-Shapley stable marriage algorithm give at least one person his or her first choice?

Given $x$ males and $x$ females with their table of priorities, does the Gale-Shapley stable marriage algorithm guarantee that at least one person gets his or her first choice? It seems like the ...
1
vote
1answer
21 views

Transitive bipartite graph

Let $G$ be a vertex-transitive bipartite graph. Then is $G$ Hamiltonian-connected? A graph is Hamiltonian-connected if for every pair of vertices there is a Hamiltonian path between the two vertices. ...
0
votes
0answers
18 views

Let $G=(X\cup Y,E)$ bipartite, such that for every $A\subseteq X$ $\lvert A\rvert\leq \lvert\Gamma(A)\rvert$

Let $G=(X\cup Y,E)$ such that for every $A\subseteq X$ $\lvert A\rvert\leq \lvert\Gamma(A)\rvert$, where $\Gamma$ is the number of neighbours. Prove that exists a match that sturates $X$. I tried ...
2
votes
1answer
58 views

How far can I get with graph theory?

I am an undergraduate who had recently finished his $2$nd year. I was wondering how far can I get with Graph Theory this summer. I am studying from Bondy & Murty's book. I already finished ...
2
votes
2answers
51 views

Finding subgraph in DAG in which all nodes are smaller than all others

I think my problem might be one of terminology, so let me explain what I am trying to do. Given a direct acyclic graph $G$ interpreted as a partial order, I want to find a subgraph $S$, so that ...
1
vote
1answer
54 views

What is the number of labeled connected graphs on $4$ or $5$ vertices?

Four vertices are labeled $1,2,3,4$. a)In how many ways can edges be drawn between some pairs of these vertices so that the result is a connected graph? b) Five vertices are labeled $1,2,3,4,5$. In ...
-2
votes
1answer
36 views

How many edges does a complete graph with n nodes have? [closed]

I know the answer but i need a mathematical prove for it. Thanks for help.
0
votes
1answer
16 views

chromatic polynomial of chordal graph

Let $G$ bei a chordal Graph. What is the chromatic polynomial of $G$? My own research on this lead me to a conference paper, "chromatic polynomials of chordal graphs" by Chandrasekharan, Madhavan and ...
4
votes
2answers
66 views

Graphs with 12 edges over the vertices $\{1,2,…,12\}$ have two vertices with a degree of 5

How many graphs with 12 edges over the vertices $\{1,2,...,12\}$ have two vertices with a degree of 5? The two vertices aren't neighbours: $\binom {10} 2 \binom 85 ^2 \binom {\binom 82} 2$. ...
2
votes
1answer
20 views

Degree Sequence of the complement graph

Given a degree sequence say, $(3,3,4,4,4,4)$ for a graph $G$, how would you quickly find the degree sequence of its the complement? In the solutions it just gives $(1,1,1,1,2,2)$. How does one know ...
1
vote
0answers
8 views

k-connectedness graph checking in matlab

A graph G is said to be k-connected (or k-vertex connected, or k-point connected) if there does not exist a set of k-1 vertices whose removal disconnects the graph, i.e., the vertex connectivity of G ...
0
votes
1answer
82 views

Proving that $\sum \deg(v) = 2m$ for any Graph $G$

Here is My proof, please correct me if wrong, I try to be formal. Proof by Induction: Let $\sum \deg(v)=2m$ assumption... when #of nodes is $n=0$. so here the equation is $\sum \deg(v)=2(0)=0$ ...
1
vote
1answer
24 views

Proving that planar, triangle free graph has vertex v with deg(v) $\leq$ 3

How do you prove that every planar, triangle-free graph (it doesn't contain $K_3$ as a subgraph) has at least one vertex that has a degree of $\leq 3$ ?
0
votes
1answer
22 views

Can we prove that $K_n$ is Hamiltonian for all $n\geq3$? [duplicate]

Can we prove that $K_n$ is Hamiltonian for all $n\geq 3$ ? I was unable to prove it. Please help me with this.
1
vote
1answer
20 views

Deriving chromatic polynomials [duplicate]

How to derive the chromatic polynomial from a Cycle? I derived the chromatic polynomial for a triangle $ K_3$ it's: $t(t-1)(t-2)$ But I don't understand how to get it for Cycles $C_n$.
1
vote
1answer
24 views

Prove there's a simple path of length $k$ in a simple graph $G$ where all the vertices have degree of at least $k$

Prove there's a simple path of length $k$ in a simple graph $G$ where all the vertices have degree of at least $k$. My attempt: Induction, for $k=1$ it's obvious. Suppose for $k-1$ and we'll ...
0
votes
2answers
25 views

Recursive equation in graph theory

How many vertex-colorings with 3 colors has the cycle $C_n$? How to build a recursive equation for the number of colorings over n? I know that a cycle has either 2 or 3 colors. 2 when n is even and ...
0
votes
0answers
11 views

The image of a a vector in the edge space when multiplied by it's incidence matrix.

Consider a graph $G=(V,E)$ and it's incidence matrix $M$. Let $\textbf{x}$ be the characteristic vector for a standard basis vector in $\mathcal{E}$ (a vector corresponding to the one element edges ...
1
vote
0answers
24 views

Properties of Connected Closed Trails?

Consider the (sub)graph below. I am allowing for the possibility of additional edges and nodes, and just want to look at the features of this subgraph. What seems apparent is that there is not a ...
1
vote
1answer
53 views

Graph Theory - K-factor

Does there exist a 47-factor of $K^{100}$? I wonder because in graph theory $k^9$ is 2-factorable for a $k$-regular spanning graph. Is there a way to come out with such a thing?
4
votes
2answers
68 views

Number of graphs such that two sides remain connected after some edges are removed

This problem was actually from a programming problem, but it has more of a math flavor, so I am asking on Math stack exchange! Problem: Initially, you are given a graph as in the first image, ...
0
votes
1answer
23 views

How can i determine the maximal length of a walk in a connected graph that goes through All the vertices

I know that a connected graph with n vertices has minimally n-1 edges but don't know how to use this information for a walk
1
vote
1answer
35 views

Maximal Distance of a graph

So I have the following graph $G = (V, E)$ with $V = [d]^n$ and $E = \{\{(a_1,\dots , a_n), (b_1, \dots , b_n)\} | a_2 = b_1 a_3 = b_2, \dots a_n = b_{n-1}\}$. That is called a $(n, d)$-dimensional ...
1
vote
1answer
21 views

Name for two cycles that share edges or are connected by a path?

Suppose I have a finite graph with nodes $I=\{i_1, i_2, \dots, i_n\}$, $i_j$ is always connected to $i_{j+1}$ for $j<n$ (hence $i_1$ need not be connected to $i_n$), and there exist two cycles $C_1 ...
10
votes
1answer
104 views

Game on simple finite graphs

Consider the following game on graphs (no multiple edges, but graphs can be disconnected). Players A and B alternate picking a vertex. After picking a vertex, a number is assigned to that vertex such ...
1
vote
1answer
36 views

Is every graph a subgraph of regular graph?

Let $G$ be a simple graph of order $n$ with maximum degree $\Delta(G)$. Is the graph $G$ a subgraph of a $r-$regular graph of order $n$ for every $r$ such that $\Delta(G)\leq r \leq n-1$ and $r\times ...
-1
votes
0answers
41 views

Colouring of Cycles - Cn

How many different ways are there to colour the cycle graph $C_n$ using only $3$ colors?? I know the chromatic polynomial: $ C_n = (t-1)^n + (-1)^n(t-1) $
0
votes
1answer
28 views

What is the proportion of edges with a certain capacity among possible edges?

Assume you have a graph with $n$ nodes/vertices and we can assign to each node a "type" : type $0$ or type 1. The types are independent. The probability of type $0$ is $$1 - \lambda \in (0,1)$$ and ...
0
votes
0answers
12 views

$k$-vertex connected minimal Steiner network problem

Could any one suggest to me a paper related to the $k$-vertex connected minimal Steiner network problem? $k$-vertex connected minimal Steiner network problem is defined as: For an undirected and ...
0
votes
0answers
32 views

constructing directed graphs using leaves of a non-isomorphic directed binary trees

I have a simple binary tree with 4 leaves: a / \ b c / \ / \ 0 1 2 3 I want to find an algorithm that constructs all directed graphs using the tree ...
3
votes
2answers
75 views

Determining graph biconnection from degree sequence

The title is self-explanatory: having the degree sequence of a graph, how can I find whether it is biconnected? The fact that I can't manage to draw one with such property does not mean that it does ...
-3
votes
1answer
54 views

problem graph theory [closed]

for a connected graph G with 50 vertices, prove that there is a walk trough all vertices with length no more than a) 98 b) 96
0
votes
1answer
42 views

Connected graph reduction problem

Graph Theory Problem 3 - please help Prove that for any connected graph $G$ there is a vertex $v$ of $G$ such that $G−v$ is still connected
5
votes
1answer
30 views

Prove that given graph consisting of vertices numbered with composite numbers is not eulerian

We have the following graph definition: $$V(G_n)=\{1\leq m\leq n : m = pq\}$$ (so vetices of $G_n$ are composite numbers) $$E(G_n)=\{\{i,j\}:i\perp j\}$$ (so vertices $i,j$ are connected if and only ...
1
vote
1answer
48 views

Homeomorphy of a surface

I am studying graphs on surfaces (i.e. maps). Their definition is below: We call map a representation $(X,\mathcal{D})$ of a finite connected graph $\Gamma=(V,E)$ in the topological surface $X$ ...
8
votes
1answer
141 views

Meeting of people.

In a group of k people, some are acquainted with each other and some are not. There are two rooms for dinner. Every person chooses to stay in that room, in which he has an even number of ...
0
votes
0answers
11 views

Marginal distribution of degrees of connected node pairs

I got this equation from Module 6CCMCS02/7CCMCS02, Theory of complex networks, compact lecture notes, from King's college London. This is the marginal distribution of connected node pairs in a ...
1
vote
1answer
44 views

Maximum nodes in AVL tree with distinct positive integers

Assuming that all keys in an AVL tree are distinct positive integers. Suppose that the root node of an AVL tree T holds the key N. What can be estimated largest possible number of nodes in T ? We ...
1
vote
0answers
41 views

counting unique paths in 2D

For a one-diemnsional sequence $\mathbf{a}=[a_1 a_2 \space … \space a_N]$, there are exactly two ways in which I can read/scan (without repetition) this sequence i-e $s_1=[a_1 \space a_2 \space … ...