# Tagged Questions

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.

38 views

### Is the triforce graph an sp-graph?

Consider the examples and the statements where a series-parallel graph (sp-graph) is defined inductively with respect to series composition and parallel composition of other sp-graphs or of $K_2$. ...
26 views

### Graph Theory Logic

So, I have this graph theory question saying that "A graph G had 6 vertices and their degrees are 2d,2d,2d+1,2d+1,2d+1 and 3d-1, show that d must be even using the sum of the edges." Now it obviously ...
38 views

### prove that if every induced subgraph of G is connected,then G is the complete graph Kn [closed]

Let G be a graph of order n prove that if every induced subgraph of G is connected,then G is the complete graph Kn
14 views

### Number of Plane Oriented Recursive Trees

The number of plane oriented recursive trees is $(2n-3)!!$ I understand that given a vertex $v$ with $k$ successors, there are $k+1$ ways to attach a new vertex to create a new tree of size one ...
49 views

### Efficient way to show Graph is a tree in proof

I am new to inductive proofs in general, and brand new to graph proofs. I am looking for an efficient way to declare that the induced subgraph prior to application of induction is, in fact, a tree. ...
52 views

### Graph and its complement that both contain Eulerian circuits

Find a graph $G$ on $7$ vertices such that both $G$ and $\overline G$ contain Eulerian circuits. $\bar G$ means complementary graph. Graph is called Eulerian circuit if the trail is closed. Please ...
39 views

### Prove $\forall$ graphs, $\alpha(G) \ge \frac{n}{\Delta(G)+1}$

Prove $\forall$ graphs, $\alpha(G) \ge \frac{n}{\Delta(G)+1}$ where $\alpha(G) :=$ maximum independent set; $\Delta(G) :=$ is the maximum degree of any vertex and $n$ is the total number of vertices. ...
56 views

### Verbal Explanation of Math Notation

I am looking at a definition for an induced subgraph. I completely understand what an induced subgraph is, so an explanation of that is beside the point. What I am really interested in is a ...
36 views

### Can a graph be strongly and weakly connected?

I'm currently revising course notes on directed graphs. It says that a directed graph (digraph) is strongly connected if there is a path between every pair of vertices. It also says that a digraph ...
31 views

### Representative System for Graph Cycles

Let $G$ be a graph containing precisely $n$ copies of $C_r$, where $n\geq 1$, $r\geq 3$, and no other cycles. Under what conditions on $n, r$ does there exist a subgraph $H\subseteq G$ that shares ...
36 views

### Is there a nontrivial perfect vertex transitive graph?

Where would one find a nontrivial (i.e. not complete multipartite) graph who is both vertex-transitive and perfect? Is there one? Edit: Perhaps I should add: apart from even cycles?
27 views

### Show that $c(G)\geq |V|-|E|$, where the equality holds iff $G$ is cycless.

Let $c(G)$ denote the number of connected components of a graph $G$. I am asked Let $G=(V,E)$. Show that $c(G)\geq |V|-|E|$, where the equality holds iff $G$ is cycless. If I'm understanding ...
36 views

### Drawing a simple graph with six vertices and varying degrees

I am attempting to solve the following problem. I have to draw a graph having the given properties or explain why no such graph exists. The conditions I am given are that it is a simple graph; with ...
86 views

### Coloring/Labelling problem in Polynomial reduction of Isomorphism

** Question :** Notice the inequality inside yellow box. If $i_1$ has $n$ possible vertex, then $j$ has maximum $(n-1)$ vertices. For $\mu_{i_1,j}$ , it should be $1\leq j \leq (n-1)$ . but it is ...
23 views

### Why is $0$ an eigen value of $L_G$?

I am learning Spectral Graph Theory. If the Laplacian Matrix of a graph $G=(V,E)$ is defined by $(a_{ij})=-1 ;(i,j)\in E, d_i ; i=j$ and $0$ otherwise then how does it follow that $0$ is an ...
39 views

### Spectrum of k-partite graph

For a given undirected graph, it is known that the signless Laplacian $Q=D+W$ is positive semidefinite, where $W$ is the adjacency matrix and $D$ is the degree matrix. In particular, the smallest ...
51 views

### Connecting up boxes mathematically (Puzzle)

How would you connect each black box once to each colored box without any lines overlapping, this is racking my brain so please help. Note that you can move the boxes where ever you want. Maybe ...
29 views

### Number of cycles of length 4 in K7

The answer to this I believe is $1/2$ * $7C3$ * $3!$ How do you arrive to this answer? I understand the $1/2$ since the graph is undirected, but nothing else. Isn't there 4 ways to choose a cycle of ...
22 views

### Add one edge to the graph such that the graph will not be 3-colourable

Could you guys help me solve this example? The question is, whether it is possible to add one new edge such that the resulting graph is not 3-colourable and prove it. I was trying to find a way to ...
29 views

### Proving in planar graph

So I have a connected triangle-free planar graph - let's name it G. So I have proven that there exists a vertex V $$deg(V)\leq 3$$ I proved that using $$m\leq 3n-6$$ where $$n=|V(G)| , m=E(G)$$ along ...
33 views

### Show that K and K' cannot both contain an Eulerian trail

For question (b), I understand how to prove that they can't both contain an Eulerian trail--eulerian trail exists if and only if there are no more than 2 odd degrees of the vertices. So for a ...
16 views

### Is there any real application of Max-Tolerance Graphs, Interval Graphs?

I have read one article about Max-Tolerance Graph:. Basically: Max-tolerance graphs can be regarded as generalized interval graphs, where two intervals $I_i$ and $I_j$ induce an edge in the ...
54 views

### Can a simple undirected graph with 11 vertices and 53 edges have a Eulerian circuit?

I have gathered these but I can't connect them properly. The sum of the degrees of the vertices is 106. So d1+d2+d3+d4+d5+d6+d7+d8+d9+d10+d11=106 To have a eulerian circuit no vertex must have an odd ...
65 views

### The maximum number of girls you can accommodate in a row

I was playing around with the following problem: 'What is the maximum number of girls in a group of boys and girls that can be seated in a row of $x$ seats so that no $n$ girls are sat next to each ...
33 views

### Maximum number of edges of a planar graph without cycles of length 3 and 4

I'm trying to calculate the maximum number of edges in a planar graph without cycles of length $3$ and $4$ (thus, $C_3$ and $C_4$). I've assumed that the condition is that the length of each face has ...
61 views

### Maximizing the sum of the products of endpoints of edges in a graph

Let $G$ be a graph with vertex set $V=\{v_1,v_2\dots v_n\}$ and edge set $E$. Let $f:V\rightarrow \mathbb [0,\infty)$ be a real valued function such that $\sum\limits_{i=1}^n f(v_i)=A$. What is the ...
24 views

### How do I properly construct a graph from an adjacency matrix?

I understand that an adjacency matrix shows connectivity between vertices but I don't get how to properly construct the graph from them. In one of my lectures I was given this adjacency matrix: ...
35 views

### The number of spanning trees of $W_4$

I need to find the number of spanning trees of $W_4$ (wheels with 5 vertices), can anyone tell me how ? I guess that the number of spanning trees is 45 spanning trees. I'm not sure how to get this. I ...
41 views

### Proof $K_3,_n$ is $n^2 3^{n-1}$

The number of spanning trees of $K_3,_n$ is $n^2 3^{n-1}$, this is true if we try by induction for any $n$ ( with n = 4, 5, . . .). is it true ?? How to prove $K_3,_n$ is $n^2 3^{n-1}$ ??
67 views

### How to algorithmically calculate the adjacency matrix of platonic solids

I need to devise a algorithm (in Python) that calculates adjacency matrices for the platonic solids. The input into the algorithm needs to be the number of polygons meeting at each vertex and the ...
82 views

### Number of distinct cycle in complete undirected graph of length $4$?

Let $G$ be a complete undirected graph on $6$ vertices. If vertices of $G$ are labeled, then the number of distinct cycles of length $4$ in $G$ is equal to $15$ $30$ $90$ $360$ My attempt : ...
72 views

### Graph theory, graph coloring, hamilton

A simple graph G has $14$ vertices and $85$ edges. Show that G must have a Hamilton circuit but does not have an Euler circuit. My attempt: to be hamilton circuit, each should have degree at least ...
280 views

### All Ihara $\zeta$ functions for planar $k$-regular graphs with a given set of faces are equivalent

This sounds like a simple piece of math (which got a long story over time, thanks for reading!) and the consequence seems surprising. At least to me. Here it is: It boils down to comparing two ...
35 views

### Star graph second-smallest eigenvalue

Prove that the star graph $K_{1,n-1}$ on $n$ vertices has $\lambda_2 = 1$, where $\lambda_2$ is the second-smallest eigenvalue of its' Laplacian. Is it true for all trees?
49 views

### Prove that a simple graph with $2n$ vertices and $n^2 +1$ edges contains a triangle for $n \ge 2$

Prove that a simple graph $G$ with $2n$ vertices and $n^2 +1$ edges contains a triangle for $n \ge 2$. I see it for $n = 2$ or $n = 3$ ... , but I fail to generalize it.
50 views

### How many trees are there on 7 vertices, where vertices 2 and 3 have degree 3, 5 has degree 2, and all others have degree 1?

How many trees are there on 7 vertices, where vertices 2 and 3 have degree 3, 5 has degree 2, and all others have degree 1? So far, I am able to determine that vertices 1, 4, 6, and 7 are leaves. My ...
24 views

### How do i prove that there are at least 12 faces of degree 5 for a regular graph of degree 3 where there are no faces of degree less than five,

how would i go about proving this? Using the handshaking lemma, the sum of the vertex degrees = 2m. So, we have $3n = 2m$. Using Euler's Formula : $n-m+f = 2,$ we have $\frac{2}{3}m - m +f = 2$ ...
54 views

### Induction: Every connected graph has a spanning tree

Definition A spanning tree of a graph $G$ is a tree $T\subseteq G$, with $V_T=V_G$ Question Proof, by induction, that every connected graph $G$ with $n$ vertices contains a spanning tree. ...
23 views

### Number of all possible orientations in a graph

What is the number of all possible orientations for an undirected graph? I think it must be $2^{|E|}$, because we have $|E|$ edges, each of them can have 2 choices for it's direction. Is it true?
101 views

### Prove that every strongly connected digraph has an odd directed cycle if its underlying graph has an odd cycle

Let D be a strongly connected digraph. Prove that if its underlying graph has an odd cycle, then D has an odd directed cycle. My first approach would be to assume that D has not such a cycle and then ...
23 views

### Is the hypercube the only connected, regular, bipartite simple finite graph?

Suppose we know that a simple graph (no multiedges or loops) with finitely many vertices is connected, regular (every vertex has the same degree), and bipartite. Must the graph be a hypercube or an ...
37 views

### How can classical random graph theory be applied to real world networks?

In real world networks, we have no further information about the structure of the networks. For example, in the Facebook network, we assume each one has some known particular probabilities to ...
27 views

### Proof that Laplacian spectrum is symmetric for bipartite graphs

Proposition. If $G$ is a bipartite graph with at least one edge, then its spectrum is symmetrical with respect to $0$, i.e. if a number $\lambda$ is an eigenvalue of $G$ then $- \lambda$ is also an ...
61 views

### Given a simple graph with $n = 4k + 2$ vertices. Can the vertices of this graph have distinct degrees?

So I was given this question that asks: Given a simple graph with $n = 4k + 2$ vertices. Can the vertices of this graph have distinct degrees? I was wondering how I would go about this. I am usually ...
56 views

### Proof that graphs are not isomorphic

If two graphs are isomorphic, they must have: the same number of vertices the same number of edges the same degrees for corresponding vertices the same number of connected components I know ...
27 views

### Using Euler's theorem to calculate the number of edges in a graph

I want to use Euler’s theorem for planar graphs to proof that for a tree $T = (V, E)$ that $|V | = |E| + 1$. Now It's very obvious that a tree is a planar graph since it is connected and there is no ...
221 views

### The number of pendant vertices in a tree

Let $T$ be a tree with vertices $\{v_1, v_2, . . . , v_n \}$ for $n \geq 2$. Prove that the number of pendant vertices in $T$ is equal to \large{2 + \sum_{v_i,deg(v_i) \geq 3}\big( deg(v_i) - 2 ...
91 views

### What does Ramsey theory tell us?

I have recently started reading about Ramsey theory, though I'm a bit confused about what does it actually tell us. As long as I understood, it says that in a big enough complete graph one can find a ...
Consider an unweighted and undirected graph $G=(V,E)$, where the vertices $V$ of $G$ lie on the unit n-sphere. If we choose a normal vector uniformly at random on this $n$-sphere, then the ...
### Prove that Graph $(V \cup W,E^{\prime})$ is connected
Suppose $(V,E)$ is a connected undirected graph, in which $V = \{v_1, v_2,..... , v_n\}$. Let $W = \{w_1,w_2,.....,w_n\}$. How can I prove that the undirected graph $(V \cup W,E^{\prime})$ is ...